1. 二分查找的基本问题

二分查找的基本问题是「力扣」第 704 题：二分查找 (opens new window)。

参考代码 1：（第 704 题代码）

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        // 在 [left..right] 里查找 target
        while (left <= right) {
            // 为了防止 left + right 整形溢出，写成这样
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                // 下一轮搜索区间：[left..mid - 1]
                right = mid - 1;
            } else {
                // 此时：nums[mid] < target，下一轮搜索区间：[mid + 1..right]
                left = mid + 1;
            }
        }
        return -1;
    }
}

说明：

二分查找的思路是：根据待搜索区间里的中间元素 nums[mid] 与 target 的值的大小关系，判断下一轮搜索需要在哪个区间里查找，进而设置 left 和 right 的值。分为如下三种情况：

• 如果 nums[mid] == target，运气很好，找到了目标元素，返回 mid ；
• 如果 nums[mid] > target，说明 mid 以及 mid 的 右边 的所有元素一定都比 target 大，下一轮搜索需要在区间 [left..mid - 1] 里查找，此时设置 right = mid - 1；
• 如果 nums[mid] < target，说明 mid 以及 mid 的 左边 的所有元素一定都比 target 小，下一轮搜索需要在区间 [mid + 1..right] 里查找，此时设置 left = mid + 1。

退出循环的时候，说明区间里不存在目标元素，返回 。