跳至主要內容

第11章 二分查找

Weiser算法二分隐藏的二分大约 13 分钟

第11章 二分查找

模板

y总的模板

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用:
int bsearch_1(int left, int right)
{
    while (left < right)
    {
        int mid = left + right >> 1;
        if (check(mid)) right = mid;    // check()判断mid是否满足性质
        else left = mid + 1;
    }
    return left;
}
// 区间[left, r]被划分成[left, mid - 1]和[mid, r]时使用:
int bsearch_2(int left, int right)
{
    while (left < right)
    {
        int mid = left + right + 1 >> 1;
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    return left;
}

书上的模板

public int search(int[] nums, int target){
	int left = 0;
    int right = nums.length-1;
    while(left <= right){
        int mid = (left + right) / 2;
        if(nums[mid] == target){
            return mid;
        }
        
        if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return -1;
}

在排序数组中的二分查找

剑指offerⅡ68:查找插入位置

给定一个排序的整数数组 nums 和一个整数目标值 target ,请在数组中找到 target ,并返回其下标。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 7
输出: 4
class Solution {
    public int searchInsert(int[] nums, int target) {
        return binarySearch(nums,0,nums.length-1,target);
    }

    private int binarySearch(int[] nums, int left, int right, int target){
        if(nums[nums.length-1]<target){
            return nums.length;//特殊情况判断
        }
        while(left < right){
            int mid = left + right >>1;
            if(nums[mid] >= target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

这个题不能写成right=mid-1left=mid,因为要根据题目的要求确定区间。

剑指offerⅡ69:山峰数组的顶部

符合下列属性的数组 arr 称为 山峰数组山脉数组)

  • arr.length >= 3
  • 存在 i0 < i < arr.length - 1)使得:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

解法一(y总模板):

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]){
                right = mid;
            }else if(arr[mid]>arr[mid-1] && arr[mid]<arr[mid+1]){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return left;
    }
}
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left=1, right=arr.length-2;
        while(left < right){
            int mid = left + right + 1>> 1;
            if(arr[mid]<arr[mid-1] && arr[mid]>arr[mid+1]){
                right = mid -1 ;
            }else if(arr[mid]>arr[mid-1] && arr[mid]<arr[mid+1]){
                left = mid;
            }else{
                return mid;
            }
        }
        return left;
    }
}

最终必须返回left,因为while的条件是left<right,跳出循环结果是left

解法二:书上的方法

没什么区别,二分范围也是[1,length-2]

剑指offerⅡ70:排序数组中只出现一次的数字

给定一个只包含整数的有序数组 nums ,每个元素都会出现两次,唯有一个数只会出现一次,请找出这个唯一的数字。

提示:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105

方法一:自己写的方法

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int length = nums.length;
        if(length == 1){
            return nums[0];
        }
        if(nums[length-1]!=nums[length-2]){
            return nums[length-1];
        }
        if(nums[0]!=nums[1]){
            return nums[0];
        }
        int left=0, right=length-1;
        while(left<right){
            int mid=left+right>>1;
            //int mid=left+right+1>>1;
            int first=-1;
            if(nums[mid]==nums[mid+1]){
                first=mid;
            }else if(nums[mid]==nums[mid-1]){
                first=mid-1;
            }
            if(first==-1){
                return nums[mid];
            }else if(first%2==1){
                right = mid;
                //right = mid-1;
            }else{
                left = mid+1;
                //left = mid;
            }
        }
        return nums[left];
    }
}

需要注意的点:

  • 需要考虑数组长度为1的情况;
  • 考虑到出现一次的数字在数组的开头和末尾,这是一种特殊情况,排除以后可以计算[1,nums.length-2]的部分,访问nums[mid+1]nums[mid-1]就不会越界;
  • first为相同的两个元素中第一个元素的下标

书上的方法改写为y总的模板:

剑指offerⅡ71:按权重生成随机数

给定一个正整数数组 w ,其中 w[i] 代表下标 i 的权重(下标从 0 开始),请写一个函数 pickIndex ,它可以随机地获取下标 i,选取下标 i 的概率与 w[i] 成正比。

例如,对于 w = [1, 3],挑选下标 0 的概率为 1 / (1 + 3) = 0.25 (即,25%),而选取下标 1 的概率为 3 / (1 + 3) = 0.75(即,75%)。

也就是说,选取下标 i 的概率为 w[i] / sum(w)

class Solution {
    private int[] sums;
    public Solution(int[] w) {
        sums = new int[w.length];
        int total = 0, i = 0;
        for(int num:w){
            total = total + num;
            sums[i++] = total;
        }
    }
    
    public int pickIndex() {
        Random random = new Random();
        int p = random.nextInt(sums[sums.length-1]);
        int left = 0, right = sums.length-1;
        while(left<right){
            int mid = left+right>>1;
            if(sums[mid]<=p){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

思路:前缀和+二分

创建另一个和权重数组长度一样的数组sums[],新数组的第i个数值sums[i]是权重数组前i个数字之和。

例如权重数组维[1,2,3,4],sums为[1,3,6,10]。随机生成一个[0,10)的数,如果在[0,1),选择下标0;如果[1,3),选择下标1;如果[3,6),选择下标2;如果[6,10),选择下标3。结果如下图所示。

随机生成一个p,找到从左往右数第一个严格大于psums[i],返回坐标i

image-20220528193313451
image-20220528193313451

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return new int[]{-1, -1};
        }
        return new int[]{findStart(nums, target), findEnd(nums, target)};
    }

    private int findStart(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left] == target ? left : -1;
    }

    private int findEnd(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

在数值范围内二分查找

剑指offerⅡ72:求平方根

剑指offerⅡ73:狒狒吃香蕉

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

狒狒可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉,下一个小时才会开始吃另一堆的香蕉。

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

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

方法一:自己写的

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int max = Integer.MIN_VALUE;
        for(int pile:piles){
            max = Math.max(max,pile);
        }
        int left=1,right=max;
        while(left<right){
            int mid=left+right>>1;
            if(isEatUp(piles,h,mid)==true){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }

    //是否能在h小时内,以速度为k吃完
    boolean isEatUp(int[] piles, int h, int k){
        int time=0;
        for(int pile:piles){
            if(pile%k==0){
                time+=pile/k;
            }else{
                time+=pile/k+1;
            }
            if(time>h){
                return false;
            }
        }
        return true;
    }
}

**方法二:书本上的方法


LC74:搜索二维矩阵Ⅰ

编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
img
img
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] firstColumn = new int[matrix.length];
        int index = 0;
        for(int[] row:matrix){
            firstColumn[index++] = row[0];
        }
        int i = searchFirstColumn(firstColumn,target);
        int j = searchRow(matrix[i],target);
        if(matrix[i][j]==target){
            return  true;
        }
        return false;
    }

    //确定该元素出现在哪一列,返回列的下标
    private int searchFirstColumn(int[] firstColumn, int target){
        int left = 0, right = firstColumn.length-1;
        while(left<right){
            int mid = left + right + 1>> 1;
            if(target>=firstColumn[mid]){
                left = mid;
            }else{
                right = mid -1;
            }
        }
        return left;
    }

    //确定该元素在该列的哪个元素
    private int searchRow(int[] row, int target){
        int left = 0, right = row.length-1;
        while(left<right){
            int mid = left + right >> 1;
            if(target <= row[mid]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return left;
    }
}

LC33:搜索旋转排序数组

整数数组 nums 按升序排列,数组中的值 互不相同

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]

给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1

image-20220528193357468
image-20220528193357468

如上图所示,在算法进行过程中,leftright的相对位置共有三种可能。

  • 对于leftright分别在两侧而言,需要判断mid在左半部分还是左半部分,接着需要判断targetmid的左侧还是右侧;
  • 对于leftright在同一侧而言,只能有nums[mid] >= nums[left],即只能进入第一个判断。然后需要判断targetmid的左侧还是右侧。
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    //这里需要注意,必须是target > nums[mid],这样才能有left = mid + 1;
                    //如果要用mid = left + right >> 1,那就必须有left = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }
        return (nums[left] == target) ? left : -1;
    }
}

LC81:搜索旋转排序数组Ⅱ

已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。

在传递给函数之前,nums 在预先未知的某个下标 k0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]

给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false

image-20220528193417542
image-20220528193417542
class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] > nums[right]) {
                //mid在前半段
                if (nums[left] <= target && target <= nums[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < nums[right]) {
                //mid在后半段
                if (target <= nums[right] && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            } else {
                right--;
            }
        }
        return nums[left] == target ? true : false;
    }
}

LC154:旋转数组中的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一次旋转,该数组的最小值为 1。

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

示例 :

输入:numbers = [2,2,2,0,1]
输出:0
image-20220528193417542
image-20220528193417542

方法一(leetcode题解中的好方法)

如上图所示,是一种最朴素的情况,用二分法解决问题,mid = left + right >> 1

  • 如果位于mid的数小于位于right的数,那么mid一定在右半边;
  • 如果位于mid的数大于位于right的数,那么mid一定在左半边;
  • 如果位于mid的数等于位于right的数,那么mid要么在左半边,要么在右半边,此时可以right--
class Solution {
    public int minArray(int[] numbers) {
        int n=numbers.length;
        return numbers[binarySearch(numbers,0,n-1)];
    }

    private int binarySearch(int[] numbers, int left, int right){
        while(left < right){
            int mid = left + right >>1;
            if(numbers[right] > numbers[mid])
                right = mid;
            else if(numbers[right] < numbers[mid])
                left = mid + 1;
            else
                right--;//其实在这一步也可以放弃二分,直接对[left,right]进行遍历,最后返回结果
        }
        return left;
    }
}

方法二(书里的方法,太过繁琐):

  • 如果numbers[mid]<=numbers[right],mid在右半边;
  • 如果numbers[mid]>=numbers[left],mid在左半边;
  • 但是存在一种特殊情况,把排序数组中的前0个数移到后面。针对这种情况,一旦发现数组中第一个数字小于最后一个,直接返回第一个数字;
  • 如果right、left、mid所指的三个数字相等,则用顺序查找到最终的答案。

隐藏的二分

LC1011:在D天内送达包裹的能力

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

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

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

示例 :

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

思路:

假设当船的运载能力为 x 时,我们可以在 days 天内运送完所有包裹,那么只要运载能力大于 x,我们同样可以在 days 天内运送完所有包裹:我们只需要使用运载能力为 x 时的运送方法即可。

这样一来,我们就得到了一个非常重要的结论:

存在一个运载能力的「下限」bottom,使得当 xbottom 时,我们可以在 days 天内运送完所有包裹;当 x<bottom 时,我们无法在 days 天内运送完所有包裹。

同时,bottom 即为我们需要求出的答案。因此,我们就可以使用二分查找的方法找出 bottom 的值。

在二分查找的每一步中,我们实际上需要解决一个判定问题:给定船的运载能力 x,我们是否可以在 days 天内运送完所有包裹呢?这个判定问题可以通过贪心的方法来解决:

由于我们必须按照数组 weights 中包裹的顺序进行运送,因此我们从数组 weights 的首元素开始遍历,将连续的包裹都安排在同一天进行运送。当这批包裹的重量大于运载能力 x 时,我们就需要将最后一个包裹拿出来,安排在新的一天,并继续往下遍历。当我们遍历完整个数组后,就得到了最少需要运送的天数。

我们将「最少需要运送的天数」与 days 进行比较,就可以解决这个判定问题。当其小于等于 days 时,我们就忽略二分的右半部分区间;当其大于 days 时,我们就忽略二分的左半部分区间。

细节

二分查找的初始左右边界应当如何计算呢?

对于左边界而言,由于我们不能「拆分」一个包裹,因此船的运载能力不能小于所有包裹中最重的那个的重量,即左边界为数组 weights 中元素的最大值。

对于右边界而言,船的运载能力也不会大于所有包裹的重量之和,即右边界为数组 weights 中元素的和。

我们从上述左右边界开始进行二分查找,就可以保证找到最终的答案。

代码:

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int n = weights.length;
        int left = Integer.MIN_VALUE, right = 0;
        for (int i = 0; i < n; i++) {
            left = Math.max(left, weights[i]);
            right += weights[i];
        }

        while (left < right) {
            int mid = left + right >> 1;
            int day = 1;
            int daySum = 0;
            for (int i = 0; i < n; i++) {
                if (daySum + weights[i] <= mid) {
                    daySum += weights[i];
                } else {
                    daySum = weights[i];
                    day++;
                }
            }
//两种写法,可以将注释部分替换掉上面的for循环。
//            int day = 0;
//            int i = 0;
//            while (i < n) {
//                int daySum = 0;
//                while (i < n && daySum + weights[i] <= mid) {
//                    daySum += weights[i++];
//                }
//                day++;
//            }
            if (day <= days) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}