二分查找
零、二分查找框架
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
//不能使用 mid = (left + right) / 2 这种方式，因为left + right可能会导致加法溢出
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
一、寻找一个数（基本的二分搜索）
即搜索一个数，如果存在，返回其索引，否则返回 -1。
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {//注意
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
注意点：
-
循环条件中是
<=，而不是<因为right的初始化赋值是
nums.length - 1，而不是nums.length，区别是：前者相当于两端都闭区间[left, right]， 后者相当于左闭右开区间[left, right)在这个算法中使用的是前者
[left, right]两端都闭的区间，这个区间其实就是我们每次进行搜索的区间找不到目标值时，我们需要通过while循环终止，然后返回-1，while循环在搜索区间为空的时候就应该终止
while(left <= right)的终止条件是left == right + 1， 写成区间的形式就是[right + 1, right]，或者带个具体的数字进去[3, 2]，可见这时候区间为空while(left < right)的终止条件是left == right，写成区间的形式就是[right, right]，或者带个具体的数字进去[2, 2]，这时候区间非空 -
left = mid + 1，right = mid - 1而不是right = mid或者left = mid这也是二分查找的一个难点，不过只要能理解前面的内容，就能够很容易判断。
刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即
[left, right]。那么当我们发现索引mid不是要找的target时，下一步应该去搜索哪里呢？当然是去搜索区间
[left, mid-1]或者区间[mid+1, right]对不对？因为mid已经搜索过，应该从搜索区间中去除。
二、寻找左侧边界的二分搜索
int left_bound(int[] nums, int target) {
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
三、寻找右侧边界的二分查找
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}