算法之二分查找优化：leetcode34:在排序数组中查找元素的第一个和最后一个位置

题干

分析

问题背景

给定一个已排序的数组，目标是找到一个给定的目标值 target 在数组中的 第一个位置 和 最后一个位置。如果目标值不存在，返回 [-1, -1]。
由于题干要求的时间复杂度是 O(log n)，并且数组是有序的，考虑使用二分法，接下来简单介绍二分法的思想：

二分查找是一种分治算法，它通过每次将搜索范围减少一半，快速查找目标值。在已排序的数组中，二分查找特别高效，时间复杂度是 O(log n)
如果你不了解二分法，推荐观看代码随想录的介绍视频
点击链接: 二分法

但是，这道题目要找的是 第一个位置 和 最后一个位置，因此我们不能只做一个普通的二分查找，而需要变种的二分查找来分别找出左边界（第一个位置）和 右边界（最后一个位置）。
找到一个符合条件（即nums[middle]==target）的时间复杂度为O(log n)，分别找两个边界的时间复杂度约为2O(log n)，依旧是O(log n)级别的。

分析题目

在普通的二分法查找中，我们通过left,right,middle指针，把数组逐渐拆分成两个部分，直至定位到符合条件（即nums[middle]==target)的下标。
但这是针对数组的的内容不重复的情况。
本题干中，数组的内容是有重复内容的，我们要算的结果，也是它的下标范围，因此当我们重新回看最经典的二分法代码：

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, 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 { // nums[mid] > target
                right = mid - 1;
            }
        }
        // 未找到目标值
        return -1;
    }
}

这是一个左闭右闭的区间，在这个区间里，每次用nums[mid]与target进行对比，再去缩小区间，在进行比较的时候，拆分成了3种情况。
第一种：nums[mid]==target，说明内容比对成功，是相等的，则直接返回。
第二种：nums[mid]<target，说明target在middle的右边，因此要把范围缩减到右半部分，left=mid+1，继续进行循环与比较。
第三种：nums[mid]>target，说明target在middle的左边，因此要把范围缩减到左半部分，right=mid-1，继续进行循环与比较。
直到不符合left<=right的条件，跳出循环。
若中间就比对成功，则直接返回下标，一直没比对成功，证明数组中没有目标值，返回-1。

而在本题中，情况略有些不同
当我们依旧使用二分法去查找目标值时，如果nums[mid]==target，并不能直接返回下标，跳出循环。因为数组中可能有2个或者更多的值，我们要查找的是一个范围，而我们比对成功的那个下标可能只是这个范围中的其中一个，因此我们要从这个点继续出发，向左右两边扩展，找到它的左边界和它的右边界。

但如果我们直接使用while循环从匹配成功的nums[mid]出发，向左右寻找它的左右边界，便不符合O(log n)的时间复杂度了。
因此我们选择分别使用二分法寻找它的左右边界，而不是先定位到一点再向左右扩展。

代码思路

我们要考虑，题干具有哪些可能的情况。
情况一

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

这是正常情况，target=8在数组中有相等的值，返回下标范围3，4

情况二

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

数组中没有匹配的值，但6在数组的nums[0]与nums[nums.length-1]之间

情况三

输入：nums = [5,7,7,8,8,10], target = 3 或target=12
输出：[-1,-1]

target在数组的范围之外

因此我们的代码，在最后进行结果的返回时，要考虑周全三种情况。
那么接下来，我们开始分别寻找leftBorder 和rightBorder

代码编写

leftBorder：寻找左边界

在经典二分法查找目标值时，我们分为了3种情况：

• nums[middle]>target
• nums[middle]<target
• nums[middle]==target

针对这三种情况，决定二分法选择左半区间还是右半区间还是直接返回。
而在本题目中，我们将进行改变，只分为2种情况：

• nums[middle]>=target
• nums[middle]<target

之所以这样分，是因为我们在寻找左边界的时候，如果nums[middle]>target时，表示我们想要找的内容在左边部分，这毋庸置疑，因此我们要缩减区间的范围。而若nums[middle]==target时，我们也不能够停下，因为它的左边可能还有匹配值，我们依旧要继续缩减区间，查找是否在左侧还有匹配内容。
若nums[middle]<target，证明目标值在右边，所以改变left指针，继续在右边查找。
所以根据这个思路，我们稍稍改写经典的二分查找代码，得到代码如下：

        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
      }

在原本的二分法代码里，将原本的3种情况改为两种。
当nums[middle]>=target时，证明左边界一定在middle的左边，这时right=middle-1，然后将right赋值给leftBorder。
之所以这样做，是因为当我们找到匹配值的时候，依旧要继续right指针改变，缩减区间，继续探索左边界。
这时候需要将匹配值左边的那个下标保存下来，如果它是左边界，当退出循环时，我们就得到了左边界。
若它不是做边界，例如左边还是target，那么它将继续二分，查找左边界，直到退出循环。

rightBorder：寻找右边界

寻找右边界的方法与寻找左边界的方法类似，代码如下：

        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }

这样，我们先定义leftBorder和rightBorder，并赋予他们一个初始值，若查找到疑似左/右边界的，他们将被赋值，若未被赋值，则证明情况为target在数组的范围之外：

例如nums = [5,7,7,8,8,10], target = 3
nums[middle]将永远大于target=3
在查找右边界的时候，rightBorder未被赋值，为初始值

例如nums = [5,7,7,8,8,10], target = 12
nums[middle]将永远小于target=12
在查找左边界的时候，leftBorder未被赋值，为初始值
可通过判断是否被赋值来判断是否target超出范围

情况分析及完整代码

综上，我们知道了如何处理变种的二分法。但所有的情况还没有考虑。
我们将leftBorder 和rightBorder赋予初始值-2
情况一

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

根据前面的代码，我们已经知道leftBorder 和rightBorder指向的是左/右范围的上一位/下一位
所以在这种情况下，leftBorder=2，rightBorder=5
由于若想查找到目标值，则需要至少一个目标值在数组之中，那么rightBorder减去leftBorder要大于1
因此条件为rightBorder-leftBorder>1

情况三

输入：nums = [5,7,7,8,8,10], target = 3 或target=12
输出：[-1,-1]

前面已经分析过，leftBorder和rightBorder为初始值时候，代表超过范围

情况二

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

这两种情况以外的情况

由此我们的完整代码如下：

class Solution {
    int[] searchRange(int[] nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{-1, -1};
    }

    int getRightBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }