Binary Search

mid的计算方式

1
2
3
4
int mid1 = right - ((right - left) >> 1);
int mid2 = left + (right - left) / 2;
当right = 5， left = 4时
mid1 = 5, mid2 = 4

总结经验

  1. 求大于(等于)target的最小值返回left

    思路：尽量执行right = mid - 1，当最后一次满足check(mid) <= target并向左滑动右区间，之后只会向右滑动左区间，最后left = right + 1退出while循环，left就是最小的最大值

    1
    2
    3
    4
    5
    6
    7
    8
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (check(mid) <= target) // mid大了
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return left;
    1. while的执行条件为left <= right
    2. if (check(mid) <= m) // mid大了 right = mid - 1;
    3. return left;

    只要nums[mid] > target，令right = mid - 1，当遇到大于target的最小值时，也会让right = mid - 1，之后在while循环中都不满足nums[mid] > target，只会执行left = mid + 1，直到left = right + 1退出while循环，此时的left便是大于target的最小值

  2. 求小于target的最大值返回right

35. 搜索插入位置

  1. 求大于等于target的最小值
  2. 如果target在数组中，则会在while循环内被return
  3. 如果target不在数组中，while会遍历到left>right结束循环
    1. 在left>right的上一步一定是left == right，此时nums[mid]<target，由于右边界是right，可以确定target一定小于nums[right + 1] (或者nums[right]已经是右边界了)
    2. 所以while退出循环时，left指向的位置是大于target的，插入在这个位置就好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target)
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return left;
    }
}

剑指 Offer II 069. 山峰数组的顶部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 1, right = arr.length - 2;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
                return mid;
            else if (arr[mid] > arr[mid - 1])
                left = mid + 1;
            else
                right = mid - 1;
        }
        return -1;
    }
}

剑指 Offer II 070. 排序数组中只出现一次的数字

优质题解,这道题需要在纸上模拟

在单一元素x之前,成对出现的第一个元素下标一定是偶数

在单一元素x之后,成对出现的第一个元素下标一定是奇数

举例

1
2
数组:1 1 2 2 3 4 4 5 5
下标:0 1 2 3 4 5 6 7 8

单一元素x的值为3,下标为4

在x之前,成对出现的元素有1 1, 2 2,第一个1的下标为0,第一个2的下标为2,均为偶数

在x之后,成对出现的元素有4 4,5 5,第一个4的下标为5,第一个5的下标为7,均为奇数

因此可以根据mid下标的奇偶性来进行二分

  • 如果mid的下标是偶数

    • 如果mid + 1 < n && nums[mid] == nums[mid + 1],那么单一元素x一定在mid + 1后,令 left = mid + 2;
    • 否则,当nums[mid] != nums[mid + 1]时,mid可能就是单一元素x,如果不是,那么x也肯定在mid前面,令right = mid

  • 如果mid的下标是奇数

    • 如果mid - 1 >= 0 && nums[mid] == nums[mid - 1],那么单一元素x一定在mid后面,令left = mid + 1

    • 否则,当nums[mid] != nums[mid - 1]时,肯定是mid - 1或者mid - 1之前出现了x,令right = mid - 1

      • 举例

        1
        2
        数组:1 2 2 4 4 
        下标:0 1 2 3 4

  • 当left == right时,退出循环,此时left(right)下标对应的数就是x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (mid % 2 == 0) {
                if (mid + 1 < n && nums[mid] == nums[mid + 1])
                    left = mid + 2;
                else 
                    right = mid;
            }
            else {
                if (mid - 1 >= 0 && nums[mid] == nums[mid - 1])
                    left = mid + 1;
                else 
                    right = mid - 1;
            }
        }
        return nums[right];
    }
}

如果nums时未排序的，那么这就是另一类经典面试题

将数组中所有数字异或，最终的结果就是那个唯一只出现一次的数字

1
2
3
4
5
6
7
8
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; ++i) 
            res = res ^ nums[i];
        return res;
    }
}

剑指 Offer II 071. 按权重生成随机数

方法一: 前缀和 + 二分查找

剑指offer题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private int total;
    private int[] preSum;
    private int n;
    public Solution(int[] w) {
        n = w.length;
        preSum = new int[n];
        for (int i = 0; i < n; ++i) {
            total += w[i];
            preSum[i] += total;
        }
    }
    
    public int pickIndex() {
        Random random = new Random();
        // 找到大于p的最小值的下标
        int p = random.nextInt(total);
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (preSum[mid] == p)
                return mid + 1;
            else if (preSum[mid] > p)
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return left;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */

剑指 Offer II 072. 求平方根

方法一：二分查找

求平方小于等于x的最大值

  1. 如果x取根号为整数，会在while循环被返回
  2. 如果x取根号不为整数，while循环不会return，结束时right = left - 1，\(right^2 < x\)并且\(left^2 > x\)， right就是所求答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 class Solution {
    public int mySqrt(int x) {
        int left = 1, right = x;
        while (left <= right) {
            int mid = right - (right - left >> 1);
            if (mid == x / mid)
                return mid;
            else if (mid < x / mid)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
}

方法二：二分查找另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int mySqrt(int x) {
        int left = 1, right = x;
        while (left <= right) {
            int mid = right - (right - left >> 1);
            if (mid <= x / mid) {
                if ((mid + 1) > x / (mid + 1))
                    return mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return 0;
    }
}

剑指 Offer II 073. 狒狒吃香蕉

方法一：二分查找

1
2
3
4
if (hours <= h) { // 吃香蕉速度太快了
    res = mid;
    right = mid - 1;
}
  1. 只要hours <= h，说明速度太快，降低速度，并且记录这次能满足hours = h的速度
  2. 之后总会进入else语句，最终left > right退出循环
  3. 最后一次记录的res就是答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = 0;
        for (int pile : piles)
            n = Math.max(n, pile);
        int left = 1, right = n,res = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int hours = getHours(mid, piles);
            if (hours <= h) { // 吃香蕉速度太快了
                res = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return res;
    }
    
    private int getHours(int speed, int[] piles) {
        int hours = 0;
        for (int pile : piles)
            hours += (pile + speed - 1) / speed;
        return hours;
    }
}

方法二：二分查找另一种写法

与方法一类似，不过不需要用一个变量记录答案

  1. 最后一次满足在h小时内吃完香蕉后，right = mid - 1,这个mid就是答案
  2. 之后一直循环else，最后left = right + 1退出循环，这个left就是最后一次满足在h小时内吃完香蕉的su'du
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int n = 0;
        for (int pile : piles)
            n = Math.max(n, pile);
        int left = 1, right = n;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int hours = getHours(mid, piles);
            if (hours <= h) { // 吃香蕉速度太快了
                right = mid - 1;
            }
            else 
                left = mid + 1;
        }
        return left;
    }
    
    private int getHours(int speed, int[] piles) {
        int hours = 0;
        for (int pile : piles)
            hours += (pile + speed - 1) / speed;
        return hours;
    }
}

278. 第一个错误的版本

和排序数组中只出现一次的数字类似

方法一：二分查找

如果isBadVersion(mid)为true，说明当前版本或者之前的版本出错，那么令right = mid - 1(即使是mid出错了)往前面搜。当遇到第一个出错的版本(我们不知道是不是第一个)，并且执行right = mid - 1，之后的while循环中只会执行else部分，

即left = mid + 1;最终left会等于right + 1并且退出while循环，这个left就是第一个出错的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 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, right = n;
        while (left <= right) {
            int mid = right - ((right - left) >> 1);
            if (isBadVersion(mid)) // 当前版本或者之前的版本出错
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }
}

162. 寻找峰值

方法一：两端添加负无穷

一定要return 0，解决只有一个数的用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 class Solution {
    public int findPeakElement(int[] arr) {
        int n = arr.length, left = 1, right = n;
        int[] nums = new int[n + 2];
        for (int i = 0; i < n; ++i)
            nums[i + 1] = arr[i];
        nums[0] = nums[n + 1] = Integer.MIN_VALUE;
        while (left <= right) {
            int mid = right - ((right - left) >> 1);
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
                return mid - 1;
            if (nums[mid] < nums[mid + 1])
                left = mid + 1;
            else 
                right = mid - 1;
        }
        return 0;
    }
}

方法二：

int mid = left + (right - left) / 2; // mid要选较小的

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length, left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2; // mid要选较小的
            if (mid + 1 < n && nums[mid] > nums[mid + 1])
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
}

367. 有效的完全平方数

方法一：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 1, right = num;
        while (left <= right) {
            int mid = right - ((right - left) >> 1);
            if (mid == num / mid && num % mid == 0)
                return true;
            if (mid > num / mid)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }
}

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

求大于target的最小值

  1. 首先判断target是否大于letters中最后一个字符，如果大于，直接返回letters[0]
  2. 进入while循环，如果letters[mid] - 'a' <= target - 'a'，令left = mid + 1，最后一次执行这个else循环的letters[mid]就是答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length - 1;
        if (target - 'a' >= letters[right] - 'a')
            return letters[0];
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (letters[mid] - 'a' > target - 'a') 
                right = mid - 1;
            else
                left = mid + 1;
        }
        return letters[left];
    }   
}

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

方法一：二分查找

二分两次，第一次找大于等于target的最小值，第二次找小于等于target的最大值，从而找到target第一个以及最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if (nums.length == 0)
            return res;
        int resL = -1, resR = -1;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        if (left >= 0 && left < nums.length)
            resL = nums[left] == target ? left : -1;
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        if (right >= 0 && right < nums.length)
            resR = nums[right] == target ? right : -1;
        res = new int[]{resL, resR};
        return res;
    }
}

410. 分割数组的最大值

优质题解

方法一：二分查找

不能写成getSplitNum(nums, mid) >= k，以下这个例子

输入：nums = [7,2,5,10,8], m = 2 输出：18 解释： 一共有四种方法将 nums 分割为 2 个子数组。 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。

如果写成getSplitNum(nums, mid) >= k，当mid=21(答案是18),得到的getSplitNum(nums, mid) = 2 >= k，会继续让mid往更大的方向搜

1
2
3
4
5
if (getSplitNum(nums, mid) > k)
    left = mid + 1;
else
    // 分割的数量太少，mid选大了
    right = mid - 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int splitArray(int[] nums, int k) {
        /*
        1.如果把数组分割成n个子数组，那么n个子数组各自和的最大值为数组中的最大值
        2.如果把数组分割成1个子数组，那么这个子数组的最大值为数组的和
        把以上两种情况返回的最大值当作二分查找的左右边界
        每次选择一个中间值mid用于分割数组，被分割的数组和必须小于等于mid，返回分割的子数组个数splitNum
        目标是确定一个恰当的「子数组各自的和的最大值」，使得它对应的「子数组的分割数」恰好等于 m
        如果splitNum > k，说明mid小了，选更大的值可以让
        * */
        int left = 0, right = 0;
        for (int num: nums) {
            if (left < num)
                left = num;
            right += num;
        }
        while (left <= right) {
            int mid = (left + right) >> 1;
            // 分割的数量太多，mid选小了
            if (getSplitNum(nums, mid) > k)
                left = mid + 1;
            else
                // 分割的数量太少，mid选大了
                right = mid - 1;
        }
        return left;
    }

    private int getSplitNum(int[] nums, int maxSum) {
        // [至少是一个分割] [当前区间的和]
        int splitNum = 1, curSum = 0;
        for (int num : nums) {
            if (curSum + num > maxSum) {
                ++splitNum;
                curSum = 0;
            }
            curSum += num;
        }
        return splitNum;
    }
}

二刷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int splitArray(int[] nums, int k) {
        int l = 0, r = 0;
        for (int x : nums) {
            r += x;
            l = Math.max(l, x);
        }
        while (l <= r) {
            int mid = (l + r) >> 1;
            // k个桶，容量上限为mid，是否能容纳所有数组元素
            if (check(nums, k, mid)) // 如果能容纳，mid上限选大了或者刚刚好
                r = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }

    private boolean check(int[] nums, int k, int mid) {
        int bucket = 1, sum = 0;
        for (int x : nums) {
            if (sum + x > mid) {
                ++bucket;
                sum = 0;
            }
            sum += x;
        }
        return bucket <= k;
    }
}

LCP 12. 小张刷题计划

和分割数组的最大值相比，加了一个条件，每个分割后的数组减去其中的最大值

getSpendDay函数，在每一个新的一天第一次要刷的题先不加入totalTime，先记录maxTime，最后少计入时长的那道题就是需要花费时间最长的题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int minTime(int[] time, int m) {
        int left = 0, right = 0;
        for (int t : time)
            right += t;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (getSpendDay(time, mid) <= m) // mid大了
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return left;
    }
    public int getSpendDay(int[] time, int limit) {
        int totalTime = 0, maxTime = 0, day = 1;
        for (int t : time) {
            int nextTime = Math.min(maxTime, t);
            if (totalTime + nextTime <= limit) {
                totalTime += nextTime;
                maxTime = Math.max(maxTime, t);
            }
            else {
                ++day;
                totalTime = 0;
                maxTime = t;
            }
        }
        return day;
    }
}

1482. 制作 m 束花所需的最少天数

方法一：二分查找

  1. 求能满足条件的最小值

  2. 如果用以下代码

    1
    2
    3
    4
    5
    if (check(bloomDay, k, mid) <= m) // 天数不够凑成m束花
        left = mid + 1;
    else 
        right = mid - 1;
    return right;

    举例

    输入：bloomDay = [1,10,3,10,2], m = 3, k = 1 输出：3 解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。 现在需要制作 3 束花，每束只需要 1 朵。 1 天后：[x, , , , ] // 只能制作 1 束花 2 天后：[x, , , _, x] // 只能制作 2 束花 3 天后：[x, , x, , x] // 可以制作 3 束花，答案为 3

    mid == 5，check(bloomDay, k, mid) == 3(m)，此时还左区间还要向右边滑动当然错了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        /**
        摘m束花的最小等待天数:能满足条件的最小值
        等待bloomDay数组中的最大元素天能摘n束花
        等待bloomDay 0天摘0束花
        在这两者之间二分
        如果选取的天数能凑成小于m束花，则left = mid + 1
        如果选取的天数能凑成大于m束花，则right = mid - 1
         */
        int n = bloomDay.length;
        if (n / m < k)
            return -1;
        int left = 0, right = 0;
        for (int flower : bloomDay)
            right = Math.max(right, flower);
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (check(bloomDay, k, mid) < m) // 天数不够凑成m束花
                left = mid + 1;
            else 
                right = mid - 1;
        }
        return left;
    }

    private int check(int[] bloomDay, int k, int days) {
        int bouquets = 0, curFlower = 0;
        for (int flower : bloomDay) {
            if (flower <= days) {
                ++curFlower;
                if (curFlower == k) {
                    ++bouquets;
                    curFlower = 0;
                }
            }
            else {
                curFlower = 0;
            }
        }
        return bouquets;
    }
    
}

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

和分割数组的最大值一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        // 把weights数组分割为days份，求最大的被分割子数组和的最小值
        // 当运载能力为数组中最大的元素时，最多n天运输完所有货物
        // 当运载能力为数组的和时，一天能运输完所有货物
        // 在这两者之间进行二分
        int n = weights.length, left = 0, right = 0;
        for (int w : weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (check(weights, mid) <= days) // 运载能力太强了
                right = mid - 1;
            else 
                left = mid + 1;
        }
        return left;
    }

    private int check(int[] weights, int capacity) {
        int total = 0, spendDay = 1;
        for (int w : weights) {
            if (total + w <= capacity) 
                total += w;
            else {
                ++spendDay;
                total = w;
            }
        }
        return spendDay;
    }
    
}

1552. 两球之间的磁力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int maxDistance(int[] position, int m) {
        /** 1.最小的最大值：尽量执行left = mid + 1,最后一次执行它后，之后都只会执行right = mid - 1
        最后right = left - 1退出循环，此时的right就是最小的最大值
        2.二分查找当前磁力(最小求间距)是否可以放得下m个球
        3.如果放得下m个球，增大球间距
        4.如果放不下m个球，减小球间距
        */
        Arrays.sort(position);
        int n = position.length, left = 1, right = position[n - 1] - position[0];
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (check(position, mid) >= m)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
    
    private int check(int[] position, int limit) {
        int pre = position[0], count = 1;
        for (int i = 1; i < position.length; ++i) {
            if (position[i] - pre >= limit) {
                pre = position[i];
                ++count;
            }
        }
        return count;
    }
    
}

Algorithms > Binary Search
#二分查找
Binary Search
https://leopol1d.github.io/2023/06/06/binary-search/
作者
Leopold
发布于
2023年6月6日
许可协议