704. 二分查找
704. 二分查找
分析
二分查找的使用有前提条件
- 有序数组
- 无重复元素
二分法经常写乱，主要是因为对搜索区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
推荐的写法是左闭右闭区间写法，即 [left, right]，此时会有如下两种结果
while (left <= right)要使用<=，因为left == right是有意义的，所以使用<=，这个其实很容易理解，假设现在有一个数组{3,5,7}，我们查找 7，我们用二分查找，首先会找到 5，然后 5 小于目标，我们会让 left 的索引更新到 2，然后查找其值，也就是num[2]，此时left==right，这个时候，如果我们设置 while 的循环条件是(left<right)，就不会检查num[2]，也就找不到目标值了，所以，允许left==right，就是为了检查[left,right]区间只有一个元素的场景，而这时有可能存在的。所以二分查找的 while 循环条件，必须是left <= right。if (nums[middle] > target)right 要赋值为middle - 1，因为当前这个nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是middle - 1
还有一点需要提醒的是，我们在写数组的题目的时候，往往会觉得，需要分情况判断 left 或者 right 下标的奇偶性和除以 2 以后的奇偶性上，其实是完全没有必要的，我们求 mid 这个中间下标，并不是要真的精确地求出中间下标，而只是想缩小 left 和 right 这个区间的范围，多一个少一个元素其实并不重要。
还有一点需要注意就是求 mid 的时候，不要写成这样 int mid = (end + start) / 2; 有可能会溢出，举个例子
public class Test {
static void main() {
System.out.println((Integer.MAX_VALUE+Integer.MAX_VALUE)/2);
}
}
输出
-1
所以我们质能写成这样
int mid = start + (end - start) / 2;
解题
public static int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
// 其实这里并不需要精确取 start 和 end 的中间，取个大概即可，只要能大约缩减一般的搜索空间即可
// int mid = (end + start) / 2; 有可能会溢出
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
二分法为什么快？
二分法快就快在，经过一次循环就可以把搜索范围缩小一半，所有的精髓，都在 right = middle - 1; 和 left = middle + 1; 上
二分查找的本质，就是有序数列的一种快速遍历方式
二分法是查找有序数组最快的方式。
有序数组，且无重复元素，且要求使用
推导过程请看 复杂度#二分查找