[算法] 二分查找及其变种问题

本文简述整数二分查找的各点注意点和诸多变种。

// Acwing 版本
终结条件为
根据if (check(mid)) 条件成立，判断答案在左区间还是右区间，如果答案在左区间并且mid也可能是答案，那么就要按模板1[l, mid], [mid + 1, r]来划分；如果答案在右区间并且mid也可能是答案，那么就要按模板2[l, mid - 1], [mid, r]来划分。
注意check(mid)要能够保证将答案分在两侧，例如找最后一个小于等于target的数，如果条件写的是target <= nums[mid]，那么如果判断为真，你的目标既有可能在mid的左侧，也有可能在mid的右侧，是没有划分效果的。如果取nums[mid] <= target则成立。

1. 版本1
   最大值最小问题，第一个>=target的元素
   // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        // 两个int相加减会溢出 中间加个长整型常量
        int mid = l + 0ll + r >> 1; 
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

2. 版本2
   最小值最大问题，最后一个<= target的元素
   //区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用，其更新操作是r = mid - 1或者l = mid。
   因为r更新为mid-1，如果mid仍然计算下取整，则l和r差1时大者永远取不到，会死循环，因此计算mid时需要加1。

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

作者：yxc
链接：https://www.acwing.com/blog/content/31/
来源：AcWing

进阶 二分答案
https://www.cnblogs.com/lcosmos/p/9438705.html

// 原始版本

• 中位数
  由于int的自动向下取整，当元素个数为偶数时，闭区间[low, high]使用求得的中位数都是下位中位数。为避免加法溢出，这种写法通常写作
• 终结条件为，使用while循环时即
  根据上述两点可以写出最常见的二分查找形式(不存在重复元素)：

int BinarySearch(int A[], int l, int r, int key) 
{ 
    int m;
    while(l <= r) 
    { 
        m = l + (r - l) / 2; 
        if(A[m] == key)
            return m;   
        if(A[m] < key)
            l = m + 1; 
        else
            r = m - 1; 
    }   
    return -1; 
} 

但这种形式每次循环需要比较两次，实际上采用下面的写法可以将比较次数优化为1次。

• 存在重复元素
  这次，采用左闭右开区间[low, high)，实际的元素个数为high - low个，注意调用时右边取数组最后元素+1的位置。
  如果实际的元素个数为偶数，求得的中位数为上位中位数；循环条件是。

// 循环不变式: A[l] <= key and A[r] > key 
int BinarySearch(int A[], int l, int r, int key) 
{ 
    int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 
  
        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 
    return l; 
} 

上述代码实际上是实现的是找出最后一个等于或小于key的元素(匹配等于key的最右边或小于key的最右边)，类似Floor并不完全相同。
如果将 A[m] <= key的条件改为 A[m] < key则找出最大的小于key的元素(小于key的最右边)

同理，如果求相反的变种问题，要返回r的时候，可以采用左开右闭区间(low, high]，调用时传入(-1, size - 1)。

// 循环不变式: A[r] >= key and A[l] < key 
int BinarySearch(int A[], int l, int r, int key) 
{ 
    int m; 
    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 
 
        if( A[m] >= key ) 
            r = m; 
        else
            l = m; 
    } 
    return r; 
} 

上述代码实际上是实现的是找出第一个等于或者大于key的元素(匹配key的最左边如果不存在则返回大于key的最左边)，即C++的lower_bound。
如果将 A[m] >= key 的条件改为 A[m] > key则找出最小的大于key的元素(大于key的最左边元素)，即C++的upper_bound。但需要注意的是上述的两种去掉等于的改动会导致可能不存在符合条件的值，因此需要加入判断 是否 A[0]>=key 或 A[r] <= key。

如果想要找出匹配值的最小下标(第一个与key相等的元素)或 最大下标(最后一个与key相等的元素)，而不考虑小于key或大于key的元素可以在上述代码返回前进行A[l]或A[r]是否等于key的判断。找到

关于这些变种问题当然也可以通过对第一种最常见的传统写法进行改写来实现，具体可以参考：https://www.cnblogs.com/luoxn28/p/5767571.html

旋转数组的二分查找
https://www.geeksforgeeks.org/the-ubiquitous-binary-search-set-1/