二分查找

发表于： 分类于：
字数： 1335 阅读：≈ 3分钟

🕧 二分查找

根据灵神的二分查找 题单 以及 视频教程 总结的二分查找模版，主要针对闭区间，左闭右开区间，开区间三种形式去找大于等于target的元素位置做了总结，并针对>，>=，<，<=四种关系做了转换，核心点在于找到循环不变量，可以理解为找到target，之后确定上下界就可以完美利用二分模版解决问题

模版

二分查找的模板适合用在查找与某一个给定元素存在一定关系的元素位置，并且给定的元素是有序的，或者元素排序不影响结果，此时可以考虑用二分查找，核心点需要确定循环不变量以及上下界，当某一个边界无法确定时，可以使用开区间，都可以确定时，使用闭区间

闭区间（推荐）

  1. 初始化：left和right需要初始化为0和len-1
  2. 循环条件：区间内没有元素的情况是left>right，所以循环条件为left<=right
  3. 结果位置：结束循环时，left和right的位置为：[right,left]，所以结果位置为left或者right+1

模板如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 找到大于等于target的第一个位置
private int lower_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {//left等于right时区间有一个元素
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else//在这里可以找到
            right = mid - 1;
    }
    return left;//返回left或者right+1
}

左闭右开区间

  1. 初始化：left和right需要初始化为0和len
  2. 循环条件：区间内没有元素的情况是left=right，所以循环条件为left<right
  3. 结果位置：结束循环时，left和right的位置为left+1=right，所以二者都可以当成结果
  4. 结果位置：结束循环时，left和right的位置为：left=right，所以结果位置为left或者right都可以

模板如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 找到大于等于target的第一个位置
private int lower_bound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {//left等于right时区间为空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    return left;//返回left或者right
}

左开右闭区间同理，只需要改变left的更新方式即可

开区间

  1. 初始化：left和right需要初始化为-1和len
  2. 循环条件：区间内没有元素的情况是left+1=right，所以循环条件为left+1<right
  3. 结果位置：结束循环时，left和right的位置为left=right，所以right可以当成结果

模板如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 找到大于等于target的第一个位置
private int lower_bound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left +1 < right) {//left+1等于right时区间为空
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid;
        else
            right = mid;
    }
    return right;//返回left+1或者right
}

关系转换

上面的模板求的是大于等于target的第一个元素出现的位置，剩下的三种情况我们可以将其转换到大于等于上面：

  1. 大于：转换成大于等于target+1

    比如大于8，此时可以转换成大于等于9

  2. 小于：转换成大于等于target的结果-1

    比如小于8，此时可以转换成大于等于8的结果位置-1

  3. 小于等于：转换成大于等于target+1的结果-1

    比如小于等于8，此时可以转换成大于等于9的结果位置-1