原理：二分法

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

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

时间复杂度：

最优时间复杂度： $O\left(1\right)$
平均时间复杂度：$O\left(\log n\right)$
最坏时间复杂度：$O\left(\log n\right)$

空间复杂度：

迭代： $O\left(1\right)$
递归：$O\left(\log n\right)$

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

边界问题

Knuth 大佬如此描述二分：思路很简单，细节是魔鬼——mid 加一还是减一，while 里到底用 <= 还是 <，没有 bug 只能靠图灵保佑。

分析二分查找时，不要写 else，尽量写 else if——可以展现出所有细节
计算 mid 时需要防止溢出，因此代码中使用 left + (right - left) / 2 替换 (left + right) / 2_{防止 left 和 right 太大}
注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查
如需定义左闭右开的「搜索区间」搜索左右边界，只要在 nums[mid] == target 时做修改即可，搜索右侧时需要减一
如果将「搜索区间」全都统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可

寻找一个数（基本的二分搜索）

搜索一个数，如果存在，返回其索引，否则返回 -1

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

while 循环条件为 <= 而非 <

该代码每次搜索的是两侧闭区间 [left, right]
循环终止条件：left == right + 1，即区间 [right + 1, right] 为空
搜索成功条件：nums[mid] == target
**left = mid + 1/right = mid - 1**：两侧闭区间，因此 mid 已经搜索过，需要从搜索空间剔除

局限性：

对于数组中存在多个 target 的情况，比如有序数组 nums = [1,2,2,2,3]，target 为 2，该算法返回 2。但如果想求 target 的左侧边界 1 或右侧边界 3，该算法是不通的。

寻找目标数的左侧边界

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;  // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)  // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        else if (nums[mid] > target)  // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        else if (nums[mid] == target) // 收缩右侧边界
            right = mid - 1;
    }
    // 判断 target 是否存在于 nums 中
    // 此时 target 比所有数都大，返回 -1
    if (left == nums.length) return -1;
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

最后需要额外判断 nums[left] 是否等于 target 就行了，如果不等于，就说明 target 不
存在不断向左收缩，达到锁定左侧边界的目的

寻找目标数的右侧边界

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 最后改成返回 left - 1
    if (left - 1 < 0) return -1;
    return nums[left - 1] == target ? (left - 1) : -1;
}

最大值最小化

注意，这里的有序是广义的有序，如果一个数组中的左侧或者右侧都满足某一种条件，而另一侧都不满足这种条件，也可以看作是一种有序（如果把满足条件看做，不满足看做，至少对于这个条件的这一维度是有序的）。换言之，二分搜索法可以用来查找满足某种条件的最大（最小）的值。

要求满足某种条件的最大值的最小可能情况（最大值最小化），首先的想法是从小到大枚举这个作为答案的「最大值」，然后去判断是否合法。若答案单调，就可以使用二分搜索法来更快地找到答案。因此，要想使用二分搜索法来解这种「最大值最小化」的题目，需要满足以下三个条件：

答案在一个固定区间内；
可能查找一个符合条件的值不是很容易，但是要求能比较容易地判断某个值是否是符合条件的；
可行解对于区间满足一定的单调性。换言之，如果是符合条件的，那么有或者也符合条件。（这样下来就满足了上面提到的单调性）

当然，最小值最大化是同理的。

优化

三分法

如果需要求出单峰函数的极值点，通常使用二分法衍生出的三分法求单峰函数的极值点。

三分法与二分法的基本思想类似，但每次操作需在当前区间 $[l,r]$（下图中除去虚线范围内的部分）内任取两点 $lmid,rmid(lmid < rmid)$（下图中的两蓝点）。如下图，如果 $f(lmid)<f(rmid)$，则在 $[rmid,r]$（下图中的红色部分）中函数必然单调递增，最小值所在点（下图中的绿点）必然不在这一区间内，可舍去这一区间。反之亦然。

在计算 $lmid$ 和 $rmid$ 时，需要防止数据溢出的现象出现。

三分法每次操作会舍去两侧区间中的其中一个。为减少三分法的操作次数，应使两侧区间尽可能大。因此，每一次操作时的 $lmid$ 和 $rmid$ 分别取 $mid-\varepsilon$ 和 $mid+\varepsilon$ 是一个不错的选择。

实现：

while (r - l > eps) {
  mid = (lmid + rmid) / 2;
  lmid = mid - eps;
  rmid = mid + eps;
  if (f(lmid) < f(rmid))
    r = mid;
  else
    l = mid;
}

划分点设置

上述二分查找一般是从二分之一处设置划分点，但比如从 1~10000 中查找 10 显然用顺序查找次数比较少。因此可以优化二分查找，使其不一定要从中间开始搜索，而是尽量找一个更接近我们要找数字的地方，以减少查找次数。
$$
P=low+(key-a[low])/(a[high]-a[low])×(high-low)
$$
这种对二分查找的优化其实有个名字，叫作插值查找，插值查找对于数列比较大并且比较均匀的数列来说，性能会好很多；但是如果数列极不均匀，则插值查找未必会比二分查找的性能好。