二分搜索

总结一下二分搜索的特性，处理问题时总遇到怎么确定 left 或者 right 的情况；

因此总结一下基本的用法，方便以后使用。

第一种判定方式：left ≤ right

如果有的题目需要得到不存在时，应在数组中的位置：

1. 如果以 left 为基准，那么最终 left 指向的位置在 target 右边；
2. 如果以 right 为基准，那么最终 right 指向的位置在 target 左边；
3. 以第一种情况为例：

class Solution {
    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 如果仅用来搜索是否存在
        // return -1;
        
        // 判断位置
        if (left > nums.length) {
            return nums[--left];
        } else if (left == 0) {
            return nums[left];
        }
        // 判断左右那个值得差更小
        if (target - nums[left - 1] < nums[left] - target) {
            return nums[left - 1];
        }
        return nums[left];
    }
}
JAVA

第二种判定方式：left < right

在得到 mid 时，常用得方法有两种：

1. mid = (right - left) / 2 + left ，避免溢出；
2. mid = (right + left) >> 1 运算更快，推荐；

class Solution {
    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] != target) {
            return -1;
        }
        return left;
    }
}
JAVA

$$
\begin{align}
&时间复杂度:O(logn)
&空间复杂度:O(1)
\end{align}
$$