算法总结之二分法

这是我参与8月更文挑战的第10天，活动详情查看：8月更文挑战

思路

首先一个区间分为两个，然后将答案确定在某个区间中，删掉另一个区间，这样每次就可以将答案范围缩小一半。

二分的流程

1. 确定二分的边界
2. 编写二分的代码框架
3. 设计一个check
4. 判断一下区间如何更新
5. 如果更新方式是l=mid， r = mid – 1，使用模版二，在算mid的时候加1

模版一

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++ 代码模板：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
复制代码

模版二

当我们将区间[l, r]划分成[l, mid – 1]和[mid, r]时，其更新操作是r = mid – 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

C++ 代码模板：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
复制代码

相关题目列表

• 69. Sqrt(x)

使用模版二，原因是所求的mid符合的条件是mid*mid <= x的时候，划分的区间是[l, mid – 1]和[mid, r]，落到了后一个区间中。

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r)
        {
            long long mid = l + r + 1ll >> 1;
            if (mid <= x / mid ) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};
复制代码

• 35. Search Insert Position

使用模版一，nums[mid] >= target所得的mid是要取的，所以划分为[l, mid]

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while(l < r) {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};
复制代码

• 34. Find First and Last Position of Element in Sorted Array

两个模版的使用

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0,r = nums.size();
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(l == nums.size() || nums[l] != target) return {-1,-1};
        int left = l;
        l = 0,r = nums.size()-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return {left,l};
    }
};
复制代码

• 33 Search in Rotated Sorted Array

/*
 * @lc app=leetcode id=33 lang=cpp
 *
 * [33] Search in Rotated Sorted Array
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return -1;
        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = (l + r) /2;
            if (nums[mid] >= target && ((nums[mid] <= nums[r] )||(target >= nums[l])))
            {
                r = mid;
            }
            else if (nums[mid] < target && target >= nums[l] && nums[mid] < nums[l])
            {
                r = mid - 1;
            }else{
                l = mid+1;
            }
            
        }
        return nums[l] == target ? l : -1;
    }
};
// @lc code=end
复制代码