模版

二分搜索：
每次将搜索空间变成原搜索空间的一半，通常要求输入有序。
时间复杂度：
O(n) = O(n/2) + O(eval) —> O(log(range))*O(eval)
O(eval)为对每个元素判断是否符合要求的时间复杂度。

左闭右开[l,r)

#return the smallest number m in range [l,r) such that g(m) is true. Return r if not found.
def binary_search(l,r):
    while l < r:
        m = l + (r-l)//2
        if g(m):
            r = m
        else:
            l = m+1
    return l

闭区间

# return the smallest number m in range [l,r] such that g[m] is true. Return r if not found
def binary_search(l,r):
    while l<=r:
        m = l + (r-l)//2
        if g[m]:
            r = m-1
        else:
            l = m+1
    return l

异同

两者的区别：

闭区间模版的循环终止条件是>=, 意味着可能需要比左闭右开的模版多循环一次。
闭区间满足g[m],更新r=m-1; 左闭右开满足g[m], 则更新为r=m.
建议使用闭区间的模版，左闭右开模版可能会有溢出的问题。

相同：

功能一致
如果没有找到满足条件的值，返回的l值都等于nums.size().

通常来说二分法的边界条件容易出错，这边采用这样的思路：
并不是试图找到准确的答案，而是找到一个分割点m, 使得对所有的n>=m, 条件g[x]都能满足。也就是说m是的g[x]成立的最小值。得到这个满足条件的最小值之后再进行一些判断。

条件函数g[x]：
不一定单调，但是存在某一个值m，满足

1 2	if x >m, g[x]>0 else g[x]<=0

upper_bound / lower_bound函数

//the first element in A which A[i] > val
upper_bound(A.begin(), A.end(), val)
//the first element in A which A[i] >= val
lower_bound(A.begin(), A.end(), val)

这两个函数是STL中使用binary search实现的两个函数。二分搜索的题目通常可以化归为“找到第一个>=val” 和"找到第一个>val"这样的pattern, 所以这边给出upper_bound 和 lower_bound的实现。

#include <iostream>
#include <vector>
using namespace std;
 
int upper_bound(const vector<int>& A, int val, int l, int r) {
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (A[m] > val)
      r = m + 1;
    else      
      l = m + 1;
  }
  return l;
}
 
int lower_bound(const vector<int>& A, int val, int l, int r) {
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (A[m] >= val)
      r = m + 1;
    else
      l = m + 1;
  }
  return l;
}
 
int main() {
  vector<int> A{1, 2, 2, 2, 4, 4, 5};
  cout << lower_bound(A, 0, 0, A.size()-1) << endl; // 0
  cout << lower_bound(A, 2, 0, A.size()-1) << endl; // 1
  cout << lower_bound(A, 3, 0, A.size()-1) << endl; // 4
  cout << upper_bound(A, 2, 0, A.size()-1) << endl; // 4
  cout << upper_bound(A, 4, 0, A.size()-1) << endl; // 6
  cout << upper_bound(A, 5, 0, A.size()-1) << endl; // 7
}

例题

35. Search Insert Position

一个有序数组，找到target的插入位置。

//namely lower_bound
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int index = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        return index;
    }
};

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

数组有序，且中有相同元素，要求找到某元素出现的首位置和末位置，如果找不到的话返回{-1,-1}.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin(); // >=
        if (l == nums.size() || nums[l] != target)
            return {-1,-1};
        int r = upper_bound(nums.begin(), nums.end(), target) - nums.begin(); // >
        return {l, r-1};
    }
};

704. Binary Search

binary search找不到返回-1

解法一：强行使用lower_bound函数

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if(l==nums.size() || nums[l]!=target)
            return -1;
        else
            return l;
    }
};

解法二：

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

875. Koko Eating Bananas

//min K s.t. sum(piles[i]/K + 1) <=8
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int l=1, r=*max_element(piles.begin(), piles.end());
        while(l <= r) {
            int m = l + (r-l)/2;
            if(needTimes(piles, m) <= H)
                r = m - 1;
            else
                l = m + 1;
        }
        return l;
    }
    
private:
    int needTimes(vector<int>& piles, int m) {
        int t = 0;
        
        for (int p : piles)
            t += (p + m - 1) / m; //除以m向上取整
        
        return t;
    }
};

Binary Search

模版

左闭右开[l,r)

闭区间

异同

upper_bound / lower_bound函数

例题

FEATURED TAGS

FRIENDS