编程笔记(三) 二分查找算法

编程笔记(三) 二分查找算法

Stop leaning useless algorithm, go and solve some problems, learn how
to use binary search.——Um_nik

通用模板

标准的二分模板至关重要。 可以二分查找的数组需要满足:

  1. 数组前面的元素都符合性质1。

  2. 数组后面的元素都符合性质2。

  3. 性质1和性质2是互斥对立的,一个元素要么属于性质1,要么属于性质2。

定义

l

l

l为符合性质1的最右侧元素的索引,

r

r

r为符合性质2的最左侧元素的索引。
显然有

r

l

=

1.

r – l = 1.

rl=1.

编程时需要将

l

l

l赋值为左边第一个满足性质1的索引,

r

r

r为右边最后一个满足性质2的索引。
如果不存在则允许越界。即默认向数组最左侧和最右侧分别添加一个满足性质1和性质2的元素。

此时定义中间值

m

i

d

=

l

+

(

r

l

)

/

/

2

mid = l + (r – l)//2

mid=l+(rl)//2,此时便不会出现

m

i

d

=

l

mid = l

mid=l

m

i

d

=

r

mid = r

mid=r无法停止循环的问题。
典型模板如下:

#include <bits/stdc++.h>
using namespace std;

int data[5] {1,3,5,6,8};

auto binary_search(int n,int target){
    //二分查找数组第一个大于等于target的位置。
    //性质1: 小于target.
    //性质2: 大于等于target.
    int l = -1;
    int r = n;
    while(r - l>1){
        int mid = l+(r - l)/2;
        auto check = [&](){
            if(data[mid]<target) return 1; //满足性质1
            else return 2;
        };
        if(check()==1) l = mid;
        else r = mid;
    }
    return r;
}

int main(){
    auto p = binary_search(5,6);
    cout<<p;//data[3] = 6,输出3.
}

C++相关库函数

lower_bound

返回第一个大于等于target的元素索引(迭代器)。 参数列表:

lower_bound(first,end,target)->iterator;

upper_bound

返回第一个大于target的元素索引(迭代器)。 参数列表:

upper_bound(first,end,target)->iterator;

binary_search

返回元素是否在指定范围中。 参数列表:

binary_search(first,end,target)->bool;

相关题目解析

力扣287-寻找重复数

链接:
寻找重复数

此题较为巧妙,因为二分的集合不是给定数组而是给定范围区间。对于处于[1,n]的整数i,记函数

f

(

i

)

f(i)

f(i)为数组中小于等于

i

i

i的元素个数,可以发现

f

(

i

)

f(i)

f(i)满足二分性。复杂度

Θ

(

n

log

(

n

)

)

\Theta(n\log(n))

Θ(nlog(n)).

代码:

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size()-1;
        int l = 0;
        int r = n;
        while(r-l>1){
            int mid = l + (r - l)/2;
            auto check = [&](){
                int cnt = 0;
                for(int i = 0;i<n+1;i++){
                    if(nums[i]<=mid) cnt++;
                }
                if(cnt<=mid) return 1;
                else return 2;
            };
            if(check()==1) l = mid;
            else r = mid;
        }
        return r;
    }
};

力扣300-最长上升子序列(LIS)问题

典型做法是

Θ

(

n

2

)

\Theta(n^2)

Θ(n2)的DP,根据Dilworth定理可以提出

Θ

(

n

log

(

n

)

)

\Theta(n\log(n))

Θ(nlog(n))的算法。
Dilworth定理的可推导出:一个数组的最长严格上升子序列长度等于最短的非严格下降子序列的划分。
于是可以通过简单模拟非严格下降子序列的划分做法(贪心+二分)求得。

代码:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int>dp(n,0);
        dp[0] = 1;
        int ans = 1;
        for(int i = 1;i<n;i++){
            int maxlen = 0;
            for(int j = 0;j<i;j++){
                if(nums[j]<nums[i]) maxlen = max(maxlen,dp[j]);
            }
            dp[i] = maxlen+1;
            ans = max(dp[i],ans);
        }
        return ans;
    }
};

概念区别

严格递增是不包含相等的递增。 非严格递增等价于非递减,包含相等的情况。

相反的概念类似。

参考资料

[1]. github-Competitive
Programming

[2]. C++二分查找库函数 lower_bound,upper_bound,binary_search
的简单使用

[3]. 力扣

[4].单调函数