本文分享自华为云社区《二分查找-一种效率较高的查找方法》，作者： i 进击的攻城狮 。
一、二分查找概述
二分查找是一种相比于逐个查找，性能更加优秀，时间复杂度更低的一种算法。
二分查找的思路是，对一个顺序的集合，确定查找区间的左右边界，再根据左右边界，计算出中间的值，再和中间值进行比较，如果左边界大于中间值，左边界向右移动到中间值+1 的位置，反之右边界移动的中间值左边的位置。
示例一：
输入: nums = [-1,0,3,5,9,12], target = 9输出: 4解释: 9 出现在 nums 中并且下标为 4
复制代码
首先左边界 left 是 0，右边界 right 是 5，
mid 中间值计算公式是：
**（右-左） / 2 + 左 **= （5-0）/2 + 0 = 2.5，向下取整为 2。
这里要注意，一般二分查找中，mid 中间下标计算结果是小数，都是向下取整。
nums[2] = 3;
3 小于目标 9，可以判断目标值在右区间。
左 = 中 + 1;
left 改变后重新计算下标，计算中间下标值是：
（5-3）/2 +3 = 4;此时数[4] = 9;
找到目标值。
代码如下
class Solution { public int search(int[] nums, int target) { int l = 0; int r = nums.length-1; while (l<=r){ int m = (r-l)+l; if (nums[m]==target){ return m; }else if (target<nums[m]){ r = m-1; }else { l = m+1; } } return -1; }}
复制代码
二、分查找解决算法问题
二分查找并不是只是简简单单的去判断一个数组中，是否存在目标值，它是一种解决问题的思想。二分查找能衍生出一些算法问题。接下来由如下三个模板，去了解如何用二分查找去解决问题。
2.1 模板 I（标准模板）
int binarySearch(int[] nums, int target){ if(nums == null || nums.length == 0) return -1; int left = 0, right = nums.length - 1; while(left <= right){ // Prevent (left + right) overflow int mid = left + (right - left) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } // End Condition: left > right return -1;}
复制代码
模板 1 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板，大多数高中或大学会在他们第一次教学生计算机科学时使用。模板 1 用于查找可以通过访问数组中的单个索引来确定的元素或条件。
在这个模板中，left 和 right 会不断靠近，最后一次遍历的时候，两个值 left 和 right 会相等。
x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
思路
在从 1 到 x 中寻找 x 的平方根，如果 mid 的平方大于 x，那么 right = mid - 1 同理，反之就是 left = mid + 1
代码：
public int mySqrt(int x) { if (x==0){return 0;} if (x==1){return 1;} int l = 0; int r = x; while(l<=r){ int m = (r-l)/2+l; if (x/m==m){ return m; }else if(x/m<m){ // 16 / 8 < 8 r = m-1; }else if(x/m>m){ l = m + 1; } } return r; }
复制代码
2.2 二分查找模板 II
分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
int binarySearch(int[] nums, int target){ if(nums == null || nums.length == 0) return -1; int left = 0, right = nums.length; while(left < right){ // Prevent (left + right) overflow int mid = left + (right - left) / 2; if(nums[mid] == target){ return mid; } else if(nums[mid] < target) { left = mid + 1; } else { right = mid; } } // Post-processing: // End Condition: left == right if(left != nums.length && nums[left] == target) return left; return -1;}
复制代码
关键属性
2.3 二分查找模板 III
模板 3 是二分查找的另一种独特形式。它用于搜索需要访问当前索引及其在数组中的直接左右邻居索引的元素或条件。
int binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) return -1; int left = 0, right = nums.length - 1; while (left + 1 < right){ // Prevent (left + right) overflow int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid; } else { right = mid; } } // Post-processing: // End Condition: left + 1 == right if(nums[left] == target) return left; if(nums[right] == target) return right; return -1;}
复制代码
点击关注，第一时间了解华为云新鲜技术~
评论