vlambda博客
学习文章列表

丨使用二分查找法的前提条件：

1.  数组是有序数组
2.  数组中无重复的数据：如果有重复，返回的元素下标可能不是唯一的

丨算法要点：

一、定义区间时满足循环不变量规则

循环不变量( loop invariant )定义：在循环过程中保持不变的性质。

保持循环不变量，就是在 while 循环时每一次边界的处理都是根据区间的定义来操作。

比如定义了目标值是在左闭右闭区间，假设 left = 0, right = nums.length - 1; 因为 right 是闭区间是要被遍历的，所以循环判断要写成 left <= right 。而不是 left < right。

之后当判断中间 middle 索引位置的值大于目标值时，right 要更新为 middle - 1 的值，而不是 right = middle。

因为进入下一次循环时也就意味着 middle 位置的值不是目标值。而我们循环判断的条件是 left <= right,如果 right = middle，middle 会再次判断一次，而我们已经知道 middle 位置的值不是目标值了，会导致程序限制死循环。

所以我们在写代码的时候，保持这个不变性质，不要造成区间一会是左闭右开，一会是左闭右闭，造成代码错误

二分法区间的定义一般为两种：左闭右闭 和 左闭右开

二、middle 取值防止越界，超出 int 的最大值

(left + right)/2 改写为：left + ((right - left) / 2)

三、使用位运算效率更快

(right - left) / 2 改写为：(right - left) >> 1

四、避免不必要的循环

      如果要寻找的目标值小于数组的最小值或者大于数组的最大值，直接返回不存在

丨复杂度分析

    空间复杂度：O(1)

丨最终代码

public int search(int[] nums, int target) { // 防止无效的查找 if (target < nums[0] || target > nums[nums.length - 1]) { return -1; } int left = 0; int right = nums.length - 1; // 定义区间的方式为左闭右闭 while (left <= right) { int middle = left + ((right - left) >> 1); if (nums[middle] > target) { right = middle - 1; } else if (nums[middle] < target) { left = middle + 1; } else { return middle; } } return -1; }