有序数列查找特定大小数的算法：二分查找（Binary Search）

凸函数或者凹函数寻找极值的算法：三分查找（Ternary Search）

二分查找

分析

以递增数组为例，将其分为两半。若中间值大于要找的数，说明要找的数在左边一半；若中间值小于要找的数，说明要找的数在右边一半。不断将范围缩小一半，直到找到要找的数。

复杂度

时间复杂度：$O(\log n)$

（$n$ 为数据规模）

代码实现

整数

  • 查找 $\ge x$ 的第一个数：

（将 if (a[mid] >= x) 改为 if (a[mid] > x) ，可查找 $> x$ 的第一个数）

// a[ ]为储存数据的有序递增数组
// l ~ r为二分查找的数组范围
int l = 0, r = n - 1;
while (l < r)
{
    int mid = (l + r) / 2;
    if (a[mid] >= x)
        r = mid;
    else
        l = mid + 1;
}
  • 查找 $\le x$ 的最后一个数：

（将 if (a[mid] <= x) 改为 if (a[mid] < x) ，查找 $< x$ 的最后一个数）

易错点：此时 $mid$ 为 $(l+r+1)/2$，若忘记 $+1$ 将会死循环。

// a[ ]为储存数据的有序递增数组
// l ~ r为二分查找的数组范围
int l = 0, r = n - 1;
while (l < r)
{
    int mid = (l + r + 1) / 2;
    if (a[mid] <= x)
        l = mid;
    else
        r = mid - 1;
}

实数

查找满足一定条件的实数：（即以下代码令 check(x) == true 的 x）

// check(int x): 判断x是否满足条件
// eps: 精度（因为浮点数误差，不可直接比大小）
// BEGIN: 查找左边界
// END: 查找右边界
bool check(int x);
double eps = 1e-6;
double l = BEGIN, r = END;
while (r - l > eps)
{
    double mid = (l + r) / 2;
    if (check(mid))
        l = mid;
    else
        r = mid;
}

algorithm 内函数

在有序递增数组中，查找 $\ge x(或> x)$ 的第一个数：

lower_bound(begin, end, num): 从数组的 begin 位置到 end - 1 位置二分查找第一个大于或等于 num 的数字，找到返回该数字的地址，不存在则返回 end。

upper_bound(begin, end, num): 从数组的 begin 位置到 end - 1 位置二分查找第一个大于 num 的数字，找到返回该数字的地址，不存在则返回 end。

在有序递减数组中，查找 $\le x(或< x)$ 的第一个数：

lower_bound(begin, end, num, greater\<type\>() ): 从数组的 begin 位置到 end - 1 位置二分查找第一个小于或等于 num 的数字，找到返回该数字的地址，不存在则返回 end。

upper_bound(begin, end, num, greater\<type\>() ): 从数组的 begin 位置到 end - 1 位置二分查找第一个小于 num 的数字，找到返回该数字的地址，不存在则返回 end。

将返回的地址减去起始地址，得到数字在数组中的下标：

int position = lower_bound(num, num + 100, 64) - num;

这样，num[position] 就是找到的第一个大于等于 64 的数字。

三分查找

分析

将 l ~ r 区间分为三份。如果 $f(m_1)<f(m_2)$，则极值点一定在区间 $(l,m_2)$；如果 $f(m_1)>f(m_2)$，则极值点一定在区间 $(m_1,r)$.

（只适用于区间内为单峰的函数）

时间复杂度

时间复杂度：$O(\log n)$

（$n$ 为数据规模）

代码实现

// f(double x): 给定区间内的凹函数或凸函数
// eps: 精度（因为浮点数误差，不可直接比大小）
// BEGIN: 查找左边界
// END: 查找右边界
double f(double x);
double eps = 1e-6;
double l = BEGIN, r = END;
while(r - l > eps)
{
    double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    if(f(m1) > f(m2)) // 此为找最小值，若要找最大值，则改为<
        l = m1;
    else
        r = m2;
}