LeetCode刷题—数组（二分法）

发表于 分类于

二分查找

目录如下：

1. 二分查找基本框架

2. 二分查找左边界

3. 二分查找右边界

相关题目：

704，二分查找

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

278，第一个错误的版本

875，爱吃香蕉的可可

1011，在D天内送达包裹的能力

69，x的平方根

744，寻找比目标字母大的最小字母

153，寻找旋转排序数组中的最小值

引入

常用的二分查找场景：寻找一个数、寻找重复数的左侧边界、寻找重复数的右侧边界。

二分查找框架
int binarySearch(int[] nums, int target) {    
    int left = 0, right = ...;
    while(...) {        
        int mid = left + (right - left) / 2;        		if (nums[mid] == target) {            
            ...        
        }else if (nums[mid] < target) {            				left = ...                           
        } else if (nums[mid] > target) {            			  right = ...        
        }    
    }    
    return ...;
}

分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。

704，二分查找，easy

给定一个升序数组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]之间。

题解：

此题是二分查找最简单的场景。通过代码理解上面框架的细节。

代码：

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) / 2;
            if(nums[mid] ==  target) return mid;
            else if(nums[mid] < target) left = mid + 1;
            else if(nums[mid] > target) right = mid - 1;
        }
        return -1;
    }
}

细节：

  1. while 内的循环条件为什么是 <= 而不是< ?

    答：初始化 right 的索引为 nums.length - 1，相当于两端都闭区间 [left, right]，这个区间其实就是每次进行搜索的区间。

    当找到目标值（nums[mid] == target）停止搜索，如果没找到，就需要while循环终止，然后返回 -1 。

    那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着没得找了，就等于没找到。

    while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

    while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

    如果非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

    //...
    while(left < right) {
        // ...
    }
    return nums[left] == target ? left : -1;

  2. 为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

    答：本题中搜索区间的两端都是闭的，[left, right]。当索引 mid 对应元素不是target，需要改变left 和 right重新搜索，搜索区间变为 [left, mid - 1] 或者 [mid + 1, right] 。

  3. 此算法的缺陷？

    答：当一个有序数组中含有多个目标值时，无法处理。例如：有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2。

引入

上面题目说明了在有序数组中找到元素 target 的方法，下面介绍 搜索左右边界 的方法。

一、寻找左侧边界的二分搜索
  • 下面是最常见的代码形式：
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意

    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

  • 细节：

    1. while 内的循环条件为什么是 < 而不是<= ?

      答：因为 right = nums.length，搜索区间是 [left,right)左闭右开。

      while终止的条件是 left == right，此时搜索区间是 [left,left)为空，可以正确终止。

    2. 为什么 left = mid + 1，right = mid？

      答：由于搜索区间左闭右开，遍历到nums[mid]之后，重新分成的两个区间应该为 [mid + 1, right) 和 [left, mid)。

    3. 为什么返回的是 left 而不是 -1 ?

      答：因为要一步一步来，先理解一下这个「左侧边界」有什么特殊含义：

      [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Qt9xu791-1611046986289)(https://gblobscdn.gitbook.com/assets%2F-MQPy5wekRlwH59Y-EnB%2Fsync%2Fda0a55ba889b5c1682dee99f8180d2bfcea66610.jpg?alt=media)]

      对于这个数组，算法会返回 1。这个 1 的含义可以这样解读：nums 中小于 2 的元素有 1 个。

      比如对于有序数组 nums = [2,3,5,7], target = 1，算法会返回 0，含义是：nums 中小于 1 的元素有 0 个。

      再比如说 nums = [2,3,5,7], target = 8，算法会返回 4，含义是：nums 中小于 8 的元素有 4 个。

      综上可以看出，函数的返回值（即 left 变量的值）取值区间是闭区间 [0, nums.length]，所以我们简单添加两行代码就能在正确的时候 return -1：

      while (left < right) {
          //...
      }
      // target 比所有数都大
      if (left == nums.length) return -1;
      // 类似之前算法的处理方式
      return nums[left] == target ? left : -1;

      另外，返回left 或 right 都可以，因为while终止的条件是 left == right。

  • 最终代码：

    int left_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int right = nums.length; // 注意

        while (left < right) { // 注意
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid; // 注意
            }
        }
        // target 比所有数都大
    	if (left == nums.length) return -1;
    	// 类似之前算法的处理方式
    	return nums[left] == target ? left : -1;
    }
二、寻找右侧边界的二分查找

与上面思想类似。

  • 代码：

    int right_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int 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;// 注意
    }

  • 细节：

    1. 为什么找右边界 left = mid + 1 ？

      答：当 nums[mid] == target 时，增大搜索区间 的下界 left，使区间向右收缩。由于搜索区间为[left,right)，则向右收缩时，新的下界为 left = mid + 1。寻找左边界向左收缩时，新的上界 right = mid。

    2. 为什么最后返回 left - 1 而不像左边界 返回 left ？

      答：while终止条件 left == right，也就是返回 right - 1。

      img

      因为对 left 的更新必须是 left = mid + 1，（也就是 mid = left - 1），while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。

    3. 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

      答：类似之前的左侧边界搜索，因为 while 的终止条件是 left == right，就是说 left 的取值范围是 [0, nums.length]，所以可以添加两行代码，正确地返回 -1：

      while (left < right) {
          // ...
      }
      if (left == 0) return -1;//注意
      return nums[left-1] == target ? (left-1) : -1;

  • 最终代码：

    int right_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        int 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; 
            }
        }
        // target 比所有数都小
        if (left == 0) return -1;
    	return nums[left-1] == target ? (left-1) : -1;
    }
34，在排序数组中查找元素的第一个和最后一个位置，medium

给定一个按照升序排列的整数数组 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

题解：

思路就是找 target 的左右边界，如果找不到就返回 [-1, -1]。

代码：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftBound = -1;
        int rightBound = -1;
        leftBound = getLeftBound(nums, target);
        rightBound = getRightBound(nums, target);
        return new int[]{leftBound, rightBound};
    } 
   //左边界
    public int getLeftBound(int[] nums, int target){
        if(nums.length == 0) return -1;
        int n = nums.length;
        int left = 0;
        int right = n;
        //左闭右开 [left,right)
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                //向左收缩
                right = mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }
        }
        if(left == n) return -1;
        return nums[left] == target? left : -1;
    }
    
    //右边界
    public int getRightBound(int[] nums, int target){
        if(nums.length == 0) return -1;
        int n = nums.length;
        int left = 0;
        int right = n;
        //左闭右开 [left,right)
        while(left < right){
            int mid = left + ( right - left)/ 2;
            if(nums[mid] == target){
                //向右收缩
                left = mid + 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }
        }
        if(left == 0) return -1;
        return nums[left - 1] == target? (left - 1): -1;
    }
}
278，第一个错误的版本，easy

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

题解

利用二分法找第一个错误的版本，搜索范围为 \([1,n)\)，左边界。

代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(isBadVersion(mid)){
                right = mid;
            }
            else    
                left = mid + 1;
        }
        return left;
    }
}
875，爱吃香蕉的可可，medium

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

提示：

1 <= piles.length <= 10^4 piles.length <= H <= 10^9 1 <= piles[i] <= 10^9

题解：

题中求在 H 小时吃掉全部香蕉的最小速度 K，即在所有可能吃完的速度中找到左边界 K，就转换为 二分法寻找左边界的问题。

对于吃的速度来说，最小为 1，最大为 max(piles)，因为每小时只能选一堆香蕉吃。

应用上面寻找左边界的框架，并根据实际场景修改。

  • 先找到数组的最大元素 maxPile
  • 在 [1, maxPile] 范围内使用二分法找 K，target 为是否能吃完香蕉。
    • 如果当前速度能吃完，向左收缩继续找。
    • 如果当前速度不能吃完，向右找。 代码：
class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int maxPile = 0;
        for(int i : piles){
            if(i > maxPile) maxPile = i;
        }
        int left = 1;
        int right = maxPile + 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(canEat(piles, mid, H)){
                //能吃完就向左收缩
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    }
    //target：当前速度是否能吃完
    public boolean canEat(int[] piles, int speed, int H){
        int time = 0;
        for(int pile : piles){
            time += timeOf(pile, speed);
        }
        return time <= H;
    }
    public int timeOf(int pile, int speed) {
        //向上取整
        return pile / speed + (pile % speed > 0 ? 1 : 0);
    }
}
1011，在D天内送达包裹的能力，medium

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

示例 2：

输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

1 <= D <= weights.length <= 50000 1 <= weights[i] <= 500

题解：

与上一题相同，是二分法在实际问题的应用。

搜索范围是 能在D天内将所有包裹送达的运载能力 [max(weights)，sum(weights)]。

寻找左边界。

target：以此运载能力 cap可以在D天全部送达

代码：

class Solution {
    public int shipWithinDays(int[] weights, int D) {
        int maxWeight = 0;
        int sum = 0;
        for(int i : weights){
            sum += i;
        }
        for(int i : weights){
            if(i > maxWeight) i = maxWeight;
        }
        int left = maxWeight;
        int right = sum + 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(canTrans(weights, D, mid)){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return left;
    }
    
    //当前运输能力为K，能否在D天运完
    public boolean canTrans(int[] w, int D, int cap){
        //运送物品个数
        int i = 0;
        //遍历D天，如果运送物品个数 = w数组元素个数，表示可以运完
        for (int day = 0; day < D; day++) {
            int maxCap = cap;
            while ((maxCap -= w[i]) >= 0) {
                i++;
                if (i == w.length)
                    return true;
            }
        }   
        return false;
    }
}
69，x的平方根，easy

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

题解：

很容易想到 x 的平方根比 x / 2 小，但事实如此吗？

解方程 \(√x < x / 2\) ，得 $x > 4 $，即 \(x = 1,2,3\) 时，平方根为 1。在写代码时就要考虑这一特殊情况。

还要注意此题向下取整，具体怎么做在代码中体现。

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x / 2;
        while(left <= right){
            int mid = left + (right - left) / 2;
            //有测试用例是 2147395599，求得 mid 平方会超过 int 范围，因此需要将平方结果转为 long 
            long sqr = (long)mid * mid;
            long sqr_next = (long)(mid + 1) * (mid + 1);
            //比如 x=8，mid=2,sqr=4,sqr_next=9。向下取整即取当前的mid。
            if(sqr == x || (sqr < x && sqr_next > x)){
               return mid;
            } 
            else if(sqr > x){
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        //返回 x 是考虑 x = 1时
        return x;
    }
}

细节

做题时对向下取整和边界问题困扰很久，这种方法比较好理解，也不用考虑那么多。

744，寻找比目标字母大的最小字母，easy

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'

示例：

输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c"

输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f"

输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f"

输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"

提示：

letters长度范围在[2, 10000]区间内。 letters 仅由小写字母组成，最少包含两个不同的字母。 目标字母target 是一个小写字母。

题解

  • 方法一：线性搜索。因为数组已排序，遍历 letters 数组，找到第一个比目标字母大的字母就返回。若都比目标字母小，则返回第一个。
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
//线性搜索
        for(int i = 0; i < letters.length; i++){
            if(letters[i] - target > 0) 
                return letters[i];        
        }
        return letters[0];
    }
}
  • 方法二：二分搜索。在 letters 数组中找到比 目标字母大的字母 中的左边界。
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0;
        int right = letters.length;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(letters[mid] - target > 0){
                right = mid;
            }
            else
                left = mid + 1;
        }
        //数组中的字符都比 target 小
        if(left == letters.length) return letters[0];
        return letters[left];
    }
}

细节

因为可能全部字母都比目标字母大，有可能找不到左边界，还要单独判断一下 left == letters.length，如果是，返回第一个字母。

153，寻找旋转排序数组中的最小值，medium

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0

示例 3：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 5000 -5000 <= nums[i] <= 5000 nums 中的所有整数都是 唯一 的 nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

  • 方法一：线性搜索。如果升序数组发生了旋转，比较相邻两元素，如果前一个元素比后一个元素大，返回后者。如果没旋转，返回首个元素即最小值。
class Solution {
    public int findMin(int[] nums) {
//线性搜索
        for(int i = 0;i < nums.length - 1; i++){
            if(nums[i] > nums[i + 1]) return nums[i + 1];
        }
        //如果不旋转，返回首个元素
        return nums[0];
    }
}

  • 方法二：二分法。此题的目的是找到数组的最小值。

    注意此时不一定是有序数组，可能发生了旋转。在找到 mid 时，要确定最小值在 mid 的左侧还是右侧。

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int min = Integer.MAX_VALUE;
        while(left <= right){
            int mid = left + (right - left) / 2;  
            //min在mid右边
            if(nums[mid] > nums[right]){
                min = Math.min(min, nums[mid]);
                left = mid + 1;
            }
            else{
                min = Math.min(min, nums[mid]);
                right = mid - 1;
            }
        }
        return min;
    }
}
------ 本文结束感谢您的阅读 ------