二分法

二分法应用场景

  • 应用一：寻找一个数，例如：二分查找
  • 应用二：寻找左侧边界，例如：在排序数组中查找元素的第一个和最后一个位置

  • 应用三：寻找右侧边界

    二分法注意事项

  • 1、left <= right 与 left < right的区别，以及它们什么时候使用

    之所以例一要使用等号，这是因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。例一和例二的区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。left <= right表示 left = right + 1时结束，而left < right表示left =right 时结束，所以为了不越界就会与right的 边界值有关 是否使用等号，在于初始化rigth是等于nums.length还是等于nums.length - 1，当right = nums.length时就不需要等号，当right = nums.length - 1时就需要等号。注意当right =nums.length时，此时由于左边界不用去，所以在收缩边界的时候，right = mid即可，不用right = mid - 1，因为此时判断条件为left = right就结束，如果right = mid - 1的话，左边界的值就会取不到。

  1.     //例一
  2.     public int search(int[] nums, int target) {
  3.         int left = 0, rigth = nums.length - 1;
  4.         while (left <= rigth) {
  5.             int mid = (left + rigth) / 2;
  6.             if (nums[mid] == target) return mid;
  7.             if (nums[mid] > target) rigth = mid - 1;
  8.             else left = mid + 1;
  9.         }
  10.         return -1;
  11.     }
  12.     //例二
  13.     public int search(int[] nums, int target) {
  14.         int left = 0, rigth = nums.length;
  15.         while (left < rigth) {
  16.             int mid = (left + rigth) / 2;
  17.             if (nums[mid] == target) return mid;
  18.             if (nums[mid] > target) rigth = mid;
  19.             else left = mid + 1;
  20.         }
  21.         return -1;
  22.     }

  • 2、什么时候left = mid + 1，left = mid和right = mid - 1，right = mid

    当初始范围为 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？ 当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。>

  • 3、左边界的二分搜索 ```java int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意

    while (left < right) { // 注意

    1.   int mid = (left + right) / 2;
    2.   if (nums[mid] == target) {
    3.       right = mid;
    4.   } else if (nums[mid] < target) {
    5.       left = mid + 1;
    6.   } else if (nums[mid] > target) {
    7.       right = mid; // 注意
    8.   }

    } return left; }

//等价于上述代码 int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; // 搜索区间为 [left, right] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收缩右侧边界 right = mid - 1; } } // 检查出界情况 if (left >= nums.length || nums[left] != target) return -1; return left; }

> 为什么上述代码可以搜索左边界，关键在于下面这段代码
> if (nums[mid] == target)         
> right = mid;
> 可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

- 右边界二分搜索，与左边界类似
```java
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = (left + right) / 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; // 注意
}