二分查找

发表于 2023-02-28 分类于算法

二分查找适用于已经排好序的数组；对可能的答案区间进行查找

二分查找

查区间[left,right]是否存在某个数字，不存在返回-1

left=0, right=n-1
while(left<=right)
在循环中判断相等情况

在排序数组中寻找是否存在一个目标值
如果不存在数组中，返回按顺序插入的位置（寻找>=target的第一个位置）

//target 大于数组中的所有数
int left=0,right=nums.size();
while(left<right){
    int mid=left+(right-left)/2;
    if(nums[mid]<target){
        left=mid+1;
    }else{
        rigth=mid;
    }
    return left;
}

69. x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        int left=0,right=x;
        while(left<right){
            int mid=left+(right-left)/2;
            if(mid+1<=x/(mid+1)){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        return left;
    }
};
//左侧可能不动，右侧必须缩小，这种可能跳不出left==right
class Solution {
public:
    int mySqrt(int x) {
        int left=0,right=x;
        while(left<right){
            long mid=((long)right+left+1)/2;
            if(mid<=x/mid)
                left=mid;
            else
                right=mid-1;
        }
        return left;
    }
};
//记录答案，使用等号
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

441. 排列硬币 - 力扣（Leetcode）

区间mid取值靠左

class Solution {
public:
    int arrangeCoins(int n) {
        if(n<=1)
            return n;
        int left=1,right=n;
        int ans=0;
        while(left<right){
            int mid=left+(right-left)/2;
            long sum=1l*(1+mid)*mid/2;
            if(sum<=n)
                left=mid+1;
            else 
                right=mid;
        }
        return left-1;
    }
};

区间mid取值靠右

有个小点需要注意的是mid = (left + right + 1) // 2
先加1再除以2是为了让中间值靠右，因为在后序对右边的值处理是 right = mid - 1
当区间只剩下两个元素的时候，判断元素大小后采用left = mid 和 right = mid - 1 这种处理方式，如果 mid 使用默认下取整的方式，在数值上 left = mid，而它对应的其中一个区间是 [mid…right]，在这种情况下，下一轮搜索区间还是 [left…right]，搜索区间没有减少，会进入死循环。

class Solution {
public:
    int arrangeCoins(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = (right - left + 1) / 2 + left;
            if ((long long) mid * (mid + 1) <= (long long) 2 * n) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

35. 搜索插入位置

比较两种写法区别

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size();
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<target)
                left=mid+1;
            else
                right=mid;
        }
        return left;
    }
};

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

算法图示

如果查找到相应的值，返回mid，num[mid]即为要查找的值

否则，退出while时，low>high，且num[low]>key，num[high]<key。

#include <iostream>
#include <vector>
using namespace std;

/*
    二分查找（折半查找）
    返回下标值，从0开始
*/
int Binary_search(vector<int> &num, int key) {
    int low = 0, high = num.size() - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (num[mid] == key)
            return mid;
        else if (num[mid] > key)
            high = mid - 1;
        else {
            low = mid + 1;
        }
    }
    cout << "low:" << low << " high:" << high << endl;
    return -1;
}

int main() {
    vector<int> num = {1, 2, 3, 4, 6, 7, 8, 9};
    cout << Binary_search(num, 5) << endl;
    return 0;
}

410. 分割数组的最大值

/*
	有问题的写法
	13   14  15
	14   14   15
	left=14符合解的条件，
*/
while(left<right){
    int mid=left+(right-left)/2;
    cout<<left<<" "<<mid<<" "<<right<<endl;
    if(checker(nums,mid)>=k)
        left=mid;
    else
        right=mid-1;
}

采用<=写法

class Solution {
public:
    int splitArray(vector<int>& nums, int k) {
        int sum=accumulate(nums.begin(),nums.end(),0);

        int left=0,right=sum;
        // cout<<left<<" "<<right<<endl;
        while(left<=right){
            int mid=left+(right-left)/2;
            // cout<<mid<<endl;
            if(check(nums,k,mid)){
                right=mid-1;
            }else
                left=mid+1;
        }
        return left;

    }

    bool check(vector<int>&nums,int k,int limit){
        int sum=0,part=1;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>limit) 
                return false;  
            if(sum+nums[i]<=limit){
                sum+=nums[i];
            }else{
                sum=nums[i];
                part++;
            }
        }
        // cout<<limit<<" "<<part<<endl;
        return part<=k;
    }
};

采用<写法

class Solution {
public:
    bool check(vector<int>& nums, int x, int m) {
        long long sum = 0;
        int cnt = 1;
        for (int i = 0; i < nums.size(); i++) {
            if (sum + nums[i] > x) {
                cnt++;
                sum = nums[i];
            } else {
                sum += nums[i];
            }
        }
        return cnt <= m;
    }

    int splitArray(vector<int>& nums, int m) {
        long long left = 0, right = 0;
        for (int i = 0; i < nums.size(); i++) {
            right += nums[i];
            if (left < nums[i]) {
                left = nums[i];
            }
        }
        while (left < right) {
            long long mid = (left + right) >> 1;
            if (check(nums, mid, m)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

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

class Solution {
  public:
    vector<int> searchRange(vector<int> &nums, int target) {
        int n = nums.size();
        if (n == 0)
            return {-1, -1};
        int first = mylower(nums, target), last = mylower(nums, target+1)-1;
        if (first == nums.size() || nums[first] != target)
            return {-1, -1};
        return {first, last};
    }
    int mylower(vector<int> &nums, int target) {
        int left = 0, right = nums.size(), mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
    int myupper(vector<int> &nums, int target) {
        int left = 0, right = nums.size(), mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] <= target)
                left = mid + 1;
            else
                right = mid;
        }
        return left - 1;
    }
};

33. Search in Rotated Sorted Array

寻找有序区间，判断targte是否位于有序区间内

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};