二分查找

算法原理：只要满足二段性即可

• 二段性：随意找一个点，把数组分为两部分，发现其中一边是可以直接排除的，这就满足二段性

模板

模板一定不要死记硬背，而是通过理解原理来记忆

---

朴素的二分模板

简单，但是适用性比较小

题目案例

• LC704. 二分查找

模板代码

int left = 0, right = nums.length - 1;

// 为什么这里是不需要等于？
// 因为新的区间内都是未知数，就算是还剩下最后一数，依然需要判断它是否满足
while (left <= right) {
    int mid = left + (right - left) / 2; // 防止溢出
    // ... 表示需要填入的内容，这个是根据二段性来填入相关的条件
    if (...) { 
        right = mid - 1;
    } else if (...) {
        left = mid + 1;
    } else {
        // 
        return ...;
    }
}

查找左/右边界的二分模板

比较复杂，但是适用性比较大，但是细节多

背诵细节（当然是要理解的去背）

• 左边界 mid 就不需要加 1，右边界 mid 就要加 1
• 下面（right)出现 -1 的时候，上面就要出现 +1

左边界

while(left < right) {
  int mid = left + (right - left) / 2;
  if (...) {
    left = mid + 1;
  } else {
    right = mid;
  }
}

右边界

while(left < right) {
  int mid = left + (right - left + 1) / 2;
  if (...) {
    left = mid;
  } else {
    right = mid - 1;
  }
}

题目案例

• LC34. 在排序数组中查找元素的第一个和最后一个位置

LC704. 二分查找

细节思考：

1. 循环条件为什么不需要加等号？ ​ 因为新的区间内都是未知数，就算是还剩下最后一数，依然需要判断它是否满足
2. 为什么更新 left, right 的时候是要加一或减一？ ​ 因为 mid 已经确认另一半区间的不可能满足条件的，mid 这个对应的值也是不满足的，所以就不需要再判断一次了

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    // 为什么这里是不需要等于？
    // 因为新的区间内都是未知数，就算是还剩下最后一数，依然需要判断它是否满足
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            return mid;
        } else {
            // nums[mid] < target
            left = mid + 1;
        }
    }

    return -1;
}

LC34. 在排序数组中查找元素的第一个和最后一个位置

这里是要用到查找左边界与右边界的二分模板

思路：

• 查找左边界

  • 结束条件是什么？为什么这样？

    

    二分查找-LC34.在排序数组中查找元素的第一个和最后一个位置-结束条件-left等于right

    1. 结束条件是 left < right 而不是 left <= right
    2. 如果有等于，在最后 —— left 等于 right mid 算出来刚好等于 left/right —— 此时走 nums[mid] == target 这个条件， left/right 就不会移动，从而陷入死循环（如图中这样的情况）

  • 如果 nums[mid] == target，应该谁来移动？怎么移动？

    1. 由于找左边界，所以相等的时候是 right 移动
    2. 因为要找的对应的下标可能就是 mid，所以 right 移动到 mid 的位置即可

  • 如果 nums[mid] != target，又应该如何移动呢？

    1. nums[mid] 太大右移，太小左移
    2. 由于 mid 这个位置的值一定可以排除，所以 left 是移动到 mid 右边，right 是移动到 mid 左边

  • mid 应该如何赋值呢？

    

    二分查找-LC34.在排序数组中查找元素的第一个和最后一个位置-mid赋值死循环情况

    1. 明确问题：mid 赋值要么是 mid = left + (right - left) / 2 要么 mid = left + (right - left + 1) / 2， 因此它只对偶数个的情况有影响，所以画图只需要画偶数的情况即可
    2. 编写相关情况：由于找左边界，所以在 nums[mid] 等于 target 的情况下，right 只会赋值为 mid， 如果 mid 赋值偏大 —— 既 mid = left + (right - left + 1) / 2 —— 此时再满足 nums[mid] == target 的条件 就会导致 right 不会移动，从而陷入死循环

• 查找右边界（与查找左边界类似，就不写了）

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int[] searchRange(int[] nums, int target) {
    int[] ret = {-1, -1};
    int n = nums.length;
    if (n == 0) return ret;
    
    // 求左端点
    int left = 0, right = n - 1;
    // 为什么这个是不能等于
    while (left < right) {
        int mid = left + (right - left) / 2; // 为什么这个不需要 +1
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    if (nums[left] == target) ret[0] = left;

    // 求右端点
    left = 0;
    right = n - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] <= target) {
            left = mid;
        } else {
            // nums[mid] > target
            right = mid - 1;
        }
    }
    if (nums[left] == target) ret[1] = left;

    return ret;
}

LC69. x 的平方根

思路：

1. 暴力解法：从 1 开始遍历 i，如果 i 的平方大于 x，那么就返回 i - 1，如果小于等于 x，那么就 i 加一
2. 根据暴力解法发现，结果值是在 [1, 4, 9, ..., n](n <= x) 这个集合内，有序数组中查找一个数，每一次查找都可以排除一批内容，符合二段性，可以用二分查找
3. 如果 pow(pow = mid * mid) 大于 x，说明太大，而且 pow 对应的 mid 也不符合要求，那么就 right 就要变为 mid - 1
4. 如果 pow 小于 x，这个值可能相等，对应的 mid 不能排除，所以 left 就变为 mid 即可
5. 如果 pow 等于 x，找到对应的 mid 了，可以直接返回
6. 循环结束还没找到，那么就是只需返回 left/right 即可

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int mySqrt(int x) {
    if (x == 0 || x == 1) return x;

    int left = 0, right = x / 2 + 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        long pow = 1l * mid * mid; // 1l 防止平方溢出
        if (pow > x) {
            right = mid - 1; // 因为大于的时候这个点也是需要排除的
        } else if (pow == x) {
            return mid;
        } else {
            // pow < x
            left = mid; // 小于的时候不能排除这个点，但是可以排除这个点左边的内容
        }
    }

    return left;
}

LC35. 搜索插入位置

思路：

1. 观察题目，发现返回值要么是相等的情况，要么是找到比 target 大的第一个数（需要考虑边界问题）
2. 分析二段性：
   • 如果 nums[mid] == target，那么直接返回
   • 如果 nums[mid] < target，排除 mid 极其左边的数，把 left 赋值为 mid + 1
   • 如果 nums[mid] > target，排除 mid 右边的数，但不能排除 mid，把 right 赋值为 mid
3. 通过二段性分析，发现 right 只能赋值 right，因此 mid 计算必须是左端点，而且结束条件为 left < right 不能有等于

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int searchInsert(int[] nums, int target) {
    // 排除最后一个的情况
    int n = nums.length;
    if (nums[n - 1] < target) return n;

    // 查找等于 或者 大于 target 的第一个数
    int left = 0, right = n - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else if (nums[mid] == target) return mid;
        else right = mid;
    }

    return left;
}

LC852. 山脉数组的峰顶索引

二段性分析：获取 mid, 发现如果 中间的值比左边大，那么就可以排除左边的内容，同理右侧也类似。

根据二段性，只需要考虑死循环的问题即可，这个问题的详细内容已经在LC34.里面有详细说明了，所以不解释了

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int peakIndexInMountainArray(int[] arr) {
    int n = arr.length;
    int left = 0, right = n - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) return mid;
        // 这里是要 arr[mid + 1] > arr[mid] 而不是 arr[mid] > arr[mid - 1], 这样是避免死循环
        else if (arr[mid + 1] > arr[mid])  left = mid + 1;
        else if (arr[mid] > arr[mid + 1])  right = mid;
    }

    return -1;
}

LC162. 寻找峰值

二段性分析：大致内容与LC852类似，还需要明确一点，就是如果往上升的方向靠近，那么一定会达到峰值

细节处理：

1. 数组只有一个元素的时候直接返回
2. 如果有且只有一个峰值，而且峰值在左/右端点，需要特意判断一下

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int findPeakElement(int[] nums) {
    int n = nums.length;
    if (n == 1) return 0;
    if (nums[0] > nums[1]) return 0;
    if (nums[n - 1] > nums[n - 2]) return n - 1;

    int left = 0, right = n - 1;
    // 只需要保证剩下的区间内至少有一个峰值即可
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid + 1] < nums[mid] && nums[mid] > nums[mid - 1]) return mid;
        else if (nums[mid] < nums[mid + 1]) left = mid + 1;
        else if (nums[mid] > nums[mid + 1]) right = mid;
    }
    return -1;
}