二分查找 - 二分查找(整数) - 《学习笔记》

概念
模板一：
- 例题
模板二：
- 例题
细节为什么有些时候取 mid 的时候需要上取整？
题型
总结
参考

概念

二分查找是一种在每次比较之后将查找空间一分为二的算法。
每次需要查找集合中的索引或元素时，都应该考虑二分查找。
如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。

三部分
二分查找一般由三个主要部分组成：

预处理 —— 如果集合未排序，则进行排序。
二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。
后处理 —— 在剩余空间中确定可行的候选者。

模板一：

标准的二分查找模板
模板 #1 用于查找可以通过访问数组中的单个索引来确定的元素。

int binarySearch(int[] nums, int target){
  if(nums == null || nums.length == 0)
    return -1;
  int left = 0, right = nums.length - 1;
  while(left <= right){
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;
    if(nums[mid] == target)
    { 
        return mid; 
    }else if (nums[mid] < target) 
    { 
        left = mid + 1; 
    } else 
    { 
        right = mid - 1; 
    }
  }
  // End Condition: left > right
  return -1;
}

关键属性

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
- 保证查找空间在每一步中至少有 1 个元素。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

区分语法

初始条件：left = 0, right = length-1
终止：left > right
向左查找：right = mid-1
向右查找：left = mid+1

例题

Acwing 789. 数的范围

704. 二分查找（简单）	数组	二分法（标准的模板1）

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

//标准的模板1类型
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

二分查找的思路是：根据待搜索区间里的中间元素 nums[mid] 与 target 的值的大小关系，判断下一轮搜索需要在哪个区间里查找，进而设置 left 和 right 的值。分为如下三种情况：

如果 nums[mid] == target，运气很好，找到了目标元素，返回 mid ；
如果 nums[mid] > target，说明 mid 以及 mid 的右边的所有元素一定都比 target 大，下一轮搜索需要在区间 [left, mid - 1] 里查找，此时设置 right = mid - 1；
如果 nums[mid] < target，说明 mid 以及 mid 的左边的所有元素一定都比 target 小，下一轮搜索需要在区间 [mid + 1, right] 里查找，此时设置 left = mid + 1。
退出循环的时候，说明区间里不存在目标元素，返回 −1。

模板二：

当看到了 **nums[mid]** 恰好等于 **target** 的时候，还得继续查找，继续看看左边的元素的值，或者继续看看右边元素的值。这时候用模板二就比模板二更合适。

例如：

大于等于 target 的下标最小的元素

小于等于 target 的下标最大的元素

int binarySearch(int[] nums, int target){
if(nums == null || nums.length == 0)
  return -1;
int left = 0, right = nums.length - 1;
while(left < right) {
  // Prevent (left + right) overflow
  int mid = left + (right - left) / 2;
  if(nums[mid] == target) { 
      return mid; 
  }
  else if (nums[mid] < target) { 
      left = mid + 1; 
  }
  else { 
      right = mid; 
  }
}
// Post-processing:
// End Condition: left == right
//这一步不是必须的，可能有也可能没有
if(nums[left] == target) 
    return left;
return -1;
}

关键属性

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
保证查找空间在每一步中至少有 2 个元素。
- 如果数组长度为0或1，不会进入while循环直接返回左值，结果也满足条件！
需要进行后处理。当你剩下 1 个元素时，循环 / 递归结束。（可能）需要评估剩余元素是否符合条件。

区分语法
初始条件：left = 0, right = length - 1
终止：left == right
向左查找：right = mid
向右查找：left = mid+1

💡
二分查找(整数) - 图1
一三为一组，二四为一组。
一三考虑一：大于等于 target 的下标最小的元素
mid = left + (right - left >> 1);
如果nums[mid] < target，left = mid + 1;否则 right = mid;
二四考虑四：小于等于 target 的下标最大的元素
mid = left + (right - left + 1 >> 1);
如果nums[mid] > target, right = mid - 1; 否则left = mid;
循环可以继续的条件 写成 while (left < right)。

在写 if 语句的时候，通常把容易想到的，不容易出错的逻辑写在 if 的里面，这样就把复杂的、容易出错的情况放在了 else 的部分，这样编写代码不容易出错。

例题

34. 在排序数组中查找元素的第一个和最后一个位置（中等）	数组	二分法（标准的模板2）
852. 山脉数组的峰顶索引（简单）	数组	二分法（标准的模板2）

34 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //返回值
        int[] result = new int[]{-1, -1};
        //特殊情况判断
        if (nums == null || nums.length == 0) {
            return result;
        }
        int left = 0;
        int right = nums.length - 1;
        //前边界二分查找
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        //后处理
        if (nums[left] != target) {
            return result;
        }
        else {
            result[0] = left;
            right = nums.length - 1;
            //后边界二分查找
            while (left < right) {
                int mid = left + right + 1 >> 1;
                if (nums[mid] > target) {
                    right = mid - 1;
                }
                else {
                    left = mid;
                }
            }
            result[1] = right;
            return result;
        }
    }
}

总结：

从数组中找第一次或最后一次出现这种表示范围的题，如果能用二分法做，应该用模板2

852 符合下列属性的数组 arr 称为山脉数组：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < … arr[i-1] < arr[i]
- arr[i] > arr[i+1] > … > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [0,2,1,0]
输出：1
示例 3：
输入：arr = [0,10,5,2]
输出：1
示例 4：
输入：arr = [3,4,5,1]
输出：2
示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

提示：
3 <= arr.length <= 104
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组

进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int mid = left + (right - left >> 1);
            if (arr[mid] < arr[mid+1]) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
}

总结：这种每次在二分的时候需要依赖mid+1位置元素的题用模板2更容易

细节为什么有些时候取 `mid` 的时候需要上取整？

回答：是否需要上取整，只和区间划分的逻辑有关。如果不调整，会出现死循环。
题34完美涵盖了这两种情况,最左值和最右值.
二分查找(整数) - 图2

题型

1. 二分下标（在数组中查找符合条件的元素的下标）

模板1 | #704 二分查找 | 💎💎经典! | | —- | —- | | #33 搜索旋转排序数组 | 💡目标元素很明显,但是原数组的顺序不是单调,要分情况讨论
先考虑中间值位于哪一部分再考虑target
时间复杂度为O(logn) | | #81 搜索旋转排序数组 II | 33的进阶,允许重复元素,最坏时间复杂度变为O(n) |
模板2 | #34 在排序数组中查找元素的第一个和最后一个位置 | 经典💎💎既有大于等于 target 的下标最小的元素,又有
小于等于 target 的下标最大的元素 | | —- | —- | | #35 搜索插入位置 | 大于等于 target 的下标最小的元素 | | #744 寻找比目标字母大的最小字母 | 大于等于 target 的下标最小的元素 | | #278 第一个错误的版本 | 大于等于 target 的下标最小的元素 | | #153 寻找旋转排序数组中的最小值 | 与33,81不同的是将寻找目标值改为找最小值 | | #154 寻找旋转排序数组中的最小值 II
#剑指 Offer 11 旋转数组的最小数字 | 153的进阶版,允许重复 | | ———————-分割线———————- | 下面的与上面的有那么点不同 | | #852 山脉数组的峰顶索引 | 判断mid与mid+1元素的相对大小,需要用到模板2 | | #1095 山脉数组中查找目标值 | 852的进阶,找到峰顶元素后再找目标元素的最小索引 | | #162 寻找峰值 | 大于等于 target 的下标最小的元素 |
既有模板1又有模板2 | #74 搜索二维矩阵 | 两次二分
第一次是模板1
第二次是模板2 | | —- | —- |

2. 二分答案（在一个有范围的区间里搜索一个整数）

定位一个有范围的整数，这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数，这个整数有明确的范围，可以考虑使用二分查找。

模板1:

#374 猜数字大小	经典!
#367 有效的完全平方数	用long类型保存平方

模板2:

#69 x 的平方根	用long类型保存平方
#29 两数相除	用long类型保存乘的结果除了二分,还用到了倍增乘法模板小于等于 `target` 的下标最大的元素
#441 排列硬币	小于等于 `target` 的下标最大的元素

3. 二分答案的升级版：判别条件需要遍历数组

#287 寻找重复数	💡有点难

4. 其它

#50 Pow(x, n)	递归类型的二分
#167 两数之和 II - 输入有序数组	多次二分
#349 两个数组的交集	多次二分
#392 判断子序列	虽然能用二分,但是时间复杂度有点高

总结

首先要关注能不能用二分？用哪种模板合适？
- 有序或者半有序数组中找下标或者确定一个有范围的整数。
能用二分后，要先确定搜索范围，例如：33. 搜索旋转排序数组（中等），81. 搜索旋转排序数组 II（中等）
可以从「看到的中间元素什么时候不是解」开始思考 if 的语句怎么写，分成可能存在和一定不存在两个区间
如果搜索区间里一定存在目标元素，退出 while (left < right) 以后，返回 left 或者 left 代表的值就可以，否则还需要单独做一次判断；例如：35. 搜索插入位置, #744 寻找比目标字母大的最小字母
有单调性一定能用二分，能用二分不一定满足单调性，二分的本质是边界具有某种性质使得一半满足，另一半不满足

参考

[1]. leetcode liweiwei1419评论总结
[2]. leetcode 官方学习文档

二分查找(整数)

概念