二分查找、三分查找

有序数列查找特定大小数的算法：二分查找（Binary Search）
凸函数或者凹函数寻找极值的算法：三分查找（Ternary Search）

二分查找

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

时间复杂度：O(log n)
（n为数据规模）

代码实现

整数

• 查找 $\geq$ x的第一个数：
  （将 if (a[mid] $\geq$ 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;
}

• 查找 $\leq$ x的最后一个数：
  （将 if (a[mid] $\leq$ 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;
}   

---

三分查找

---

分析
将数组分为三份，分别对应数组的左中右三个位置。若左中右三个位置的函数值在同一侧，则将数组缩小到左中右三个位置；若左中右三个位置的函数值在不同侧，则将数组缩小到中间两个位置。不断缩小数组范围，直到找到极值。

时间复杂度：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;
}