跳到主要内容
版本：0.17.0+

二分查找

例一：递减序列中找第一个比目标值小的元素​

假定我们要查找一个非严格递减数组中第一个小于目标值的位置。也就是反向的upper_bound函数。

id0123
val7552

根据经验，我们设计的函数接口是 int findFirstLess(int s, int t, int v)，其中区间为左开右闭[s, t)。

查找 0，该值比数组中所有值都小，所以理应返回 t=3，即区间右端点位置 3​

我们的目标是要查找第一个比目标值小的元素位置。

当中点元素比目标值大时，比如 5 > 0，因此目标值应该在中点右端，且不包含中点。

此外，若中点元素与目标值相等，同上。

而当中点元素比目标值小时，由于序列时递减的，则目标元素必定在中点元素左边，但可能包含中点。

因此，中点与目标值的判断函数为：

if(A[m] >= v) s = m + 1;
else t = m;

以下给出手动模拟，当查找 0 时，将返回 3，程序通过。

s = 0, t = 3, m = (s + t) >> 1 = 1;

A[1] = 5 > 0 => s = m + 1 = 2;

s = 2, t = 3, m = (s + t) >> 1 = 2;

A[2] = 5 > 0 => s = m + 1 = 3;

s = 3, t = 3; return 3;

查找 7，比 7 小的第一个元素是 5，且位于下标 1 处，应返回 1​

s = 0, t = 3, m = 1;

A[1] = 5 < 7 => t = m = 1;

s = 0, t = 1, m = 0;

A[0] = 7 >= 7 => s = m + 1 = 1;

s = 1, t = 1; return 1;

程序通过。

查找 9，比 9 小的第一个元素是 7，下标为 0，应返回 0​

s = 0, t = 3, m = 1;

A[1] = 5 < 9 => t = m = 1;

s = 0, t = 1, m = 0;

A[0] = 7 < 9 => t = m = 0;

s = 0, t = 0; return 0;

程序通过。

完整代码​

int findFirstLess(int nums[], int s, int t, int v)
{
  while(s < t)
  {
    int m = s + ((t - s) >> 1);
    nums[m] >= v ?  s = m + 1 : t = m;
  }
  return s;
}

例二：递增序列中找第一个比目标值大的元素​

同上，容易写出以下代码。

完整代码​

int findFirstGreater(int nums[], int s, int t, int v)
{
  while(s < t)
  {
    int m = s + ((t - s) >> 1);
    nums[m] <= v ?  s = m + 1 : t = m;
  }
  return s;
}