解题关键的地方：在遇到等于 target 的元素的时候，还需要继续搜索下去。具体来说：

  • 目标元素有可能在 mid 这个位置；
  • 目标元素有可能在 mid 的左边；
  • 目标元素一定不会在 mid 的右边。

所以，当 nums[mid] == target 成立的时候，下一轮搜索区间是 [left..mid]，所以设置 right = mid。

参考代码：

public class Solution {

    public int search(int[] nums, int target) {
        int len = nums.length;
        // 特殊判断
        if (len == 0) {
            return -1;
        }

        // 在区间 [left..right] 里查找 target 第一次出现的位置
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                // 下一轮搜索区间在 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索区间在 [left..mid]
                right = mid;
            }
        }

        // 退出循环以后 left 与 right 重合，还需要再做一次判断
        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
}

代码细节解释：

写 while (left < right) 是为了保证 退出循环以后 left == right 成立。

永远考虑下一轮搜索区间是什么。

遇到的情况就 3 种：

  • 情况 1：nums[mid] < target，mid 的左边一定不存在 target，下一轮搜索区间 [mid + 1..right]，此时设置 left = mid + 1；
  • 情况 2：nums[mid] = target，题解最开始已经分析了，此时设置 right = mid。
  • 情况 3：nums[mid] > target，mid 的右边一定不存在 target，下一轮搜索区间 [left..mid - 1]，此时设置 right = mid - 1。

合并「情况 2」和「情况 3」，只把区间分成 2 个部分：「一定不存在目标元素的区间」和「可能存在目标元素的区间」，这样退出循环以后才有 left == right 成立。

复杂度分析：

  • 时间复杂度：，这里 是输入数组的长度；
  • 空间复杂度：，只使用了常数个空间。