二分查找

2021-01-02

二分查找

1. 写一个正确的二分查找程序

需要注意的是，二分查找有许多注意的地方，比如循环中止条件是什么，left 和 right 初始值是什么。下面以Leetcode 704号问题，写一个基本的二分查找算法。

/**
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;// 前闭后闭的取值范围 对应着循环结束时，要取等号。
        while(left <= right){ // 此时取值范围里只有一个数字。
            int mid = left + (right - left) /2; // 防止 left + right 越界
            if(nums[mid] == target){
                return mid;
            }
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return -1;
}

2. left的意义是什么

我们可以看最后要跳出循环时，也就是left = right时，此时mid = left = right,如果数组中存在这个元素，自然返回mid索引，如果不存在呢，回到以下代码：

if(nums[mid] > target){
    right = mid - 1;
}else{
    left = mid + 1;
}

left的位置恰好就是该元素插入到该数组的位置。当nums[mid] > target时，如果要将target插入到数组中，要将nums[mid]元素向后移一个位置，空出来的位置就是应该插入的位置，也就是left指向的位置。如果小于呢，left = mid + 1,此时left会向后移一位，恰好又是应该插入的位置。

由此解决Leetcode 35号问题。

/**
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。
*/
public int searchInsert(int[] nums, int target) {
        //解决target不存在数组中时，返回要插入的位置
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            }
            if(target > nums[mid]){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
}

3. 其他相关问题

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

这是Leetcode 34号问题。

/**
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-		sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public  int[] searchRange(int[] nums, int target) {
       int first = -1, second = -1;
       first = lower_boud(nums,target);
       second = upper_boud(nums,target);
       int ans[] = new int[]{first,second};
       return ans;
   }
// 以下是辅助函数
   private int lower_boud(int arr[], int target){
       //利用二分搜索查找target在数组中最左边位置
       int left = 0, right = arr.length - 1,res = -1;
       while (left <= right){
           int mid = left + (right - left) / 2;
           if (target == arr[mid]){
               res = mid;
               //逼近左边界,继续向左
               right = mid - 1;
           }else if (target < arr[mid]){
               right = mid - 1;
           }else{
               left = mid + 1;
           }

       }
       return res;
   }

   private int upper_boud(int arr[], int target){
       int left = 0, right = arr.length - 1,res = -1;
       while (left <= right){
           int mid = left + (right - left) / 2;
           if (target == arr[mid]){
               res = mid;
               //逼近右边界,继续向右
               left = mid + 1;
           }else if (target < arr[mid]){
               right = mid - 1;
           }else{
               left = mid + 1;
           }

       }
       return res;
   }

3.2 第一个错误的版本

这是Leetcode 278号问题。

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

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

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

示例:

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-bad-version
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public int firstBadVersion(int n) {
       int left = 1, right = n;
       while (left <= right) {
           int mid = left + (right - left) / 2;
           if (isBadVersion(mid) == true) {// 已经是错误版本，看看之前的版本有没有错
               right = mid - 1;
           } else {// 正确版本，看往后的版本有没有错
               left = mid + 1;
           }
       }
       return left;
   }

还是看一下边界条件，当left = right = mid, 如果isBadVersion(mid) == true成立，表明这就是第一个错误版本，返回left；否则，表明mid是一个正确版本，那么left = mid + 1; left 就是第一个错误的版本。

3.3 寻找峰值

这是Leetcode 162号问题

/**
峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public int findPeakElement(int[] nums) {
        if (nums.length == 1) {
           return 0;
       }
       int left = 0, right = nums.length -1;
       while (left < right) {
           int mid = left + (right - left) / 2;
           if (nums[mid] > nums[mid + 1]) {
               right = mid;
           } else {
               left = mid + 1;
           }
       }
       return left;
   }

类似的还有Leetcode 852号问题。

/**
我们把符合下列属性的数组 A 称作山脉：

A.length >= 3
存在 0 < i < A.length - 1 使得A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] 的 i 的值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/peak-index-in-a-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
class Solution {
    public int peakIndexInMountainArray(int[] A) {
        int left = 0, right = A.length - 1; 
		 while (left <= right) {
	            int mid = left + (right - left) / 2;
	            int v = A[mid];
	            // 按照定义，peak元素后至少有一个比他小的元素，因此不必担心越界
             	if (v < A[mid + 1]) {
	                left = mid + 1;
	            } else {
	                right = mid - 1;
	            }
	        }
	    return left;
    }
}

注意：以上两道题在边界处理方面有所不同，应当注意取分。

考虑852号问题边界情况，最后一次循环已经到了“峰顶”元素，且此时left = right = mid，由于A[mid]为“峰顶”元素，且其后面至少有一个元素，那么A[mid] > A[mid+1]（mid+1没有越界），因此执行right = mid - 1，又right < left，跳出循环，返回left。

Leetcode 1095号问题。

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */
 
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        // 最小的index
        // [1,2,3,4,5,3,1]
        int len = mountainArr.length();
        int peak = findPeak(0, len - 1, mountainArr);
        int l = searchLeft(0, peak, target, mountainArr);
        return l == -1 ? searchRight(peak, len - 1, target, mountainArr) : l;
    }

    // 找到山峰值
    private int findPeak(int left, int right, MountainArray mountainArray) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int v = mountainArray.get(mid);
            // 由于题中定义peak后面会有一个元素，因此不会越界
            if (v < mountainArray.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // 左边找 [0, peak]严格升序数组
    int searchLeft(int left, int right, int target, MountainArray mountainArray) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int v = mountainArray.get(mid);
            if (v == target) {
                return mid;
            }
            if (v > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    // [peak,len-1]右边是严格降序数组
    private int searchRight(int left, int right, int target, MountainArray mountainArray)	{
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int v = mountainArray.get(mid);
            if (v == target) {
                return mid;
            }
            if (v > target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

3.4 Pie

杭电oj 1969

题目大意为：

给定$n$个不同半径的派（高度均为1，口味互不相同），有$f + 1$个人，求一个最大体积$V$，使得这$n$个派可以分为$f+1$份（不可以多个不同口味的派拼起来凑成$V$）。可以发现最大体积一定不会大于最大派的体积$Max$，因此在区间$[0,Max]$中进行二分搜索就可以。

#include <iostream>
#include <stdio.h>
#include <cmath>

using namespace std;

const double pi = acos(-1.0);
int t, f, n, r[10005], MAX;
int check(double v){
    int cnt = 0;
    for(int i = 0; i < n; i++){
        double tmp = r[i] * r[i] * pi;
        cnt += floor(tmp / v);
    }
    if(cnt >= (f + 1)){
        return 1;
    }
    return 0;
}
int main()
{
    cin >> t;
    while(t--){
        cin >> n >> f;
        MAX = -1;
        for(int i = 0; i < n; i++){
            cin >> r[i];
            MAX = max(MAX, r[i]);
        }
        double left = 0.0, right = MAX * MAX * pi, mid;
        // 在0 - 最大面积中选一个值使得所有pie能够分成 f+1份
        while(right - left >= 1e-7){
            mid = (left + right) / 2.0;
            // check mid，是否可以分成 f+1
            if(check(mid) == 1){// 还可以继续增大搜索
                left = mid + 1e-6;
            }else{ // 不够分了，要减小
                right = mid - 1e-6;
            }
        }// 最后跳出循环时left = right
        printf("%.4lf\n", left);

    }
    return 0;
}

4. 利用二分法求解方程

杭电oj 2199

说的是给定函数$8x^4 + 7x^3 + 2x^2 + 3x + 6 == Y$，针对输入的不同的$Y$，求出$x$在区间$[0,100]$上的解，要求最终$x$精确到小数点后4位。

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
int t;
double y;
double f(double x){
    return 8.0 * pow(x,4.0) + 7.0 * pow(x, 3.0) + 2.0 * pow(x, 2.0) + 3.0 * x + 6.0;;
}
int main()
{
    cin >> t;
    while(t--){
        cin >> y;
        // 函数在[0,100]上是单调递增的
        if(y < f(0) || y > f(100)){
            cout << "No solution!\n";
        }else{
            // 二分查找
            double left = 0.0, right = 100.0, mid;
            while(right - left >= 1e-6){
                mid = (left + right) / 2.0;
                double tmp = f(mid);
                if(tmp > y){
                    right = mid - 1e-7;
                }else{
                    left = mid + 1e-7;
                }
            }
            // 最终left right趋于一个值
            printf("%.4lf\n", (left + right) / 2);
        }
    }
    return 0;
}

杭电oj 2899

给定函数$f(x) = 6x^7 + 8x^6 + 7x^3 + 5x^2 -yx,x\in[0,100]$，对于给定的不同的$y$值，求出$f(x)$在$[0,100]$上的最小值（精确到小数点后4位）。

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
int t;
double y;
double f(double x, double y){
    return 6.0 * pow(x, 7) + 8.0 * pow(x, 6) + 7.0 * pow(x, 3)
            + 5.0 * pow(x, 2) - y * x;
}

double df(double x){
    return 42.0 * pow(x, 6) + 48.0 * pow(x, 5) + 21.0 * pow(x, 2) + 10.0 * x;
}
int main()
{
    cin >> t;
    while(t--){
        cin >> y;
        /**
        针对给定的y，求出df中使得df(x) = y 的x值，判定x是否在[0,100]中，若在
        则x就是极小值点，带入f中求得极小值
        若不在, 在f(0)与f(100)中取最小值
        */
        double left = 0.0, right = 100.0, mid, ans, x_star;
        if(y < df(0) || y > df(100)){//x_star 不在[0,100]之间
            ans = min(f(0.0,y),f(100.0,y));
        }else{
            while(right - left > 1e-7){
                mid = (left + right) / 2.0;
                if(df(mid) > y){
                    right = mid - 1e-6;
                }else if(df(mid) < y){
                    left = mid + 1e-6;
                }
            }
            x_star = (left + right) / 2.0;
            ans = f(x_star, y);
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}

5. 三分法

二分法能够有效解决有序序列的问题，然而当一个序列先增大后减小（或者先减小后增大）即存在一个峰值时，就要用到三分的思想了。三分和二分有点像，三分是在left和right指针区间内，设置$mid1$、$mid2$两个指针，即$mid1$与$mid2$将$[left，right]$区间三等分。之后根据具体问题更新left和right指针位置，即可能：$left = mid1$或者$right = mid2$。

例子：求解函数$f(x) = x^2 -4x + 3,x \in [0,5]$上的极小值。

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

double f(double x){
    return x * x - 4 * x + 3;
}
int main()
{
    double left = 0.0, right = 5.0, mid1, mid2;
    while(right - left > 1e-8){
        mid1 = left + (right - left) / 3.0;
        mid2 = right - (right - left) / 3.0;
        // 求[0,5]区间f的极小值
        if(f(mid1) > f(mid2)){ // mid2对应的点更小
            left = mid1;
        }else{
            right = mid2;
        }
    }
    double min_value = f(left);
    printf("%.6lf\n",min_value);
    printf("%.6lf\n",left);
    return 0;
}