整数二分查找原理及代码模板

1.整数二分算法原理

• ps：数组具有单调性，则一定可以使用整数二分算法；但是，能够使用整数二分算法的数组，数组未必具有单调性。
• 整数二分算法的本质：给定一个区间，在区间中定义了某种性质。该性质在区间的右半区间是满足的，但在左半区间是不满足的。二分法的目的就是为了寻找满足某种性质的分界点。
• 算法主要步骤：
  • a.确定区间的中间点mid
  • b.根据实际问题编写check()函数，判断mid是否满足区间[l, r]的某种性质
  • c.更新区间端点

• 模板1图解：

  
  模板1.png

• 模板2图解：

  
  模板2.png

2.代码模板1

// 根据实际题目场景编写check()函数，检查x是否满足某种性质
bool check(int x) 
{

}


// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
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;
}

3.代码模板2

// 根据实际题目场景编写check()函数，检查x是否满足某种性质
bool check(int x) 
{

}

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用
int bsearch_1(int l, int r)
{
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;  // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}