704. 二分查找
704. 二分查找
分析
二分查找的使用有前提条件
- 有序数组
- 无重复元素
二分法经常写乱，主要是因为对搜索区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在 while 寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。
推荐的写法是左闭右闭区间写法，即[left, right]，此时会有如下两种结果 while (left <= right)要使用<=，因为left == right是有意义的，所以使用<=if (nums[middle] > target)right 要赋值为middle - 1，因为当前这个nums[middle]一定不是 target，那么接下来要查找的左区间结束下标位置就是middle - 1
还有一点需要提醒的是，我们在写数组的题目的时候，往往会觉得，需要分情况判断 left 或者 right 下标的奇偶性和除以 2 以后的奇偶性上，其实是完全没有必要的，我们求 mid 这个中间下标，并不是要真的精确地求出中间下标，而只是想缩小 left 和 right 这个区间的范围，多一个少一个元素其实并不重要。
解题
public static int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
while (start <= end) {
// 其实这里并不需要精确取 start 和 end 的中间，取个大概即可，只要能大约缩减一般的搜索空间即可
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; 上
二分查找的本质，就是有序数列的一种快速遍历方式
二分法是查找有序数组最快的方式。
有序数组，且无重复元素，且要求使用