二分法

思路

首先一个区间分为两个,然后将答案确定在某个区间中,删掉另一个区间,这样每次就可以将答案范围缩小一半。
70% 满足单调性
95% 存在两段性

二分的流程

  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;
}

相关题目列表

使用模版二,原因是所求的 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;
    }
};

使用模版一,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;
    }
};

两个模版的使用

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

  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...