二分法

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

工作原理

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

int binary_search(int start ,int end ,int key)
{
    int back=-1;//未搜索到返回-1
    int mid;
    while(start<=mid)
    {
        mid=start+((end-start)>>1);
        if(a[mid]<key)
            start=mid+1;
        else if(a[mid]>key)
            end=mid-1;
        else
        {// 最后检测相等是因为多数搜索情况不是大于就是小于
            back=mid;
            break;
        }
    }
    return back;
}

C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound,二者均定义于头文件 <algorithm> 中。二者均采用二分实现，所以调用前必须保证元素有序。

int A[100005];  // 示例全局数组
int lower(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) > 0) && compare(a, b) > 0)
    return 1;
  else if (b != A && compare(a, b - 1) <= 0)
    return -1;  // 用到地址的减法，因此必须指定元素类型
  else
    return 0;
}// 查找首个不小于待查元素的元素的地址
int upper(const void *p1, const void *p2) {
  int *a = (int *)p1;
  int *b = (int *)p2;
  if ((b == A || compare(a, b - 1) >= 0) && compare(a, b) >= 0)
    return 1;
  else if (b != A && compare(a, b - 1) < 0)
    return -1;  // 用到地址的减法，因此必须指定元素类型
  else
    return 0;
}// 查找首个大于待查元素的元素的地址

三分法

三分法可以用来查找凸函数的最大（小）值。

画一下图能够帮助理解（图待补）

如果 lmid 和 rmid 在最大（小）值的同一侧：由于单调性，一定是二者中较大（小）的那个离最值近一些，较远的那个点对应的区间不可能包含最值，所以可以舍弃。

如果在两侧：由于最值在二者中间，我们舍弃两侧的一个区间后，也不会影响最值，所以可以舍弃。

lmid = left + (right - left >> 1);
rmid = lmid + (right - lmid >> 1);  // 对右侧区间取半
if (cal(lmid) > cal(rmid))
  right = rmid;
else
  left = lmid;