关于leetCode第34题引发的二分查找的思考

原题

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

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

示例 2：

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

示例 3：

1 2	输入：nums = [], target = 0 输出：[-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

在这个题目中比较明显的就是需要使用二分查找法来进行算法的简化，但是二分查找法一般用来查找某个指定的数字，而在这个题目中，需要查找比指定数字大的和小的数字。

首先在解题过程中写出的代码如下：

public int[] searchRange(int[] nums, int target) {
	var output = new int[]{-1, -1};
    int len = nums.length;
    if (len == 0)
    	return new int[]{-1, -1};
    if (len == 1)
        return target == nums[0] ? new int[]{0, 0} : new int[]{-1, -1};
    int low = 0;
    int high = len - 1;
    int mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (nums[mid] >= target)
    	    high = mid - 1;
        else
            low = mid + 1;
    }
    if (nums[mid] == target)
        output[0] = mid;
    low = 0;
    high = len - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (nums[mid] <= target)
    	    low = mid + 1;
        else
            high = mid - 1;
    }
    if (mid - 1 >= 0 && nums[mid - 1] == target)
       output[1] = mid - 1;
    return output;
}

在这个版本的代码下很容易发现进行的二分查找虽然能够正确的找到下限，但是当输入如下时

1
2

[2,2]
2

并不能得到理想的输出，检查代码后发现，由于是使用二分查找法，如果整个序列没有比查找数字更大的数是上线的返回一定是错误的，因为二分查找无法返回越界的下标，所以我对这个函数进行了一定的优化。核心思想是判断在计算上限时所需要的-1的动作是否会导致答案错误，改动之后的代码如下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        var output = new int[]{0, 0};
        int len = nums.length;
        if (len == 0)
            return new int[]{-1, -1};
        if (len == 1)
            return target == nums[0] ? new int[]{0, 0} : new int[]{-1, -1};
        int low = 0;
        int high = len - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] >= target)
                high = mid - 1;
            else
                low = mid + 1;
        }
        output[0] = mid;
        low = 0;
        high = len - 1;
        mid = (low + high) / 2;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] <= target)
                low = mid + 1;
            else
                high = mid - 1;
        }

        if (nums[len - 1] == target || mid == 0) {
            output[1] = mid;
        } else {
            output[1] = mid - 1;
        }
        return nums[output[0]] == target && nums[output[1]] == target ? output : new int[]{-1, -1};
    }
}

这段代码虽然已经解决了上述的问题，但是经过运行发现还是错误的，复查后发现因为普通的二分法的弱mid下标直接指向target相同的数字，那么将会直接返回，否则更改上下限下标直接舍去mid下标以避免死循环的出现。但是在这个题目中，需要考虑是否舍去的就恰好是需要查找的数。所以不能在循环体执行结束之后对mid值进行记录而需要在循环过程中对返回的下标做不断的更新，最终能够得到答案。

在这个思路上，我们对代码进行了整体的重构，在上文的代码中读者应该注意到了while循环体中的内容大致相同，所以我们将两个循环体进行抽象，提取出一个函数，具体代码如下：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

需要注意的是while循环体中的一个条件判断对mid下标的存储。刚开始可能会有疑问，为何对mid下标的更新仅发生在这个指定的条件下而另一个分支则不对mid进行更新。这里需要注意的是只有满足在if中的条件的语句的条件下计算出的mid才是有效的，在另一个分支中计算出的mid一定是无效数据，是错误的，所以不需要进行记录。

同时可以看到在主方法体中，对最后的两个下标进行了验算，针对target不存在的情况进行了排除，最终就可以得到正确的答案。

续

在这种思路中通过ans对二分查找的过程变量进行存储。最后进行输出，我个人认为这种方法在一定程度上更加难理解，可以使用二分查找的排除法进行进一步的改写，让代码更符合逻辑思维。

排除思想

首先需要改写的就是循环条件在上述条件中ans的作用就是对计算过程中的ans进行迭代的存储，而为了避免对ans的取值情况的思考，可以改变循环体的条件为while(left<right)这个循环体在推出循环时满足条件left=right所以仅需要返回任意一个值即可。

步骤

循环体的条件为while(left<right)
写if-else语句的时候对排除情况进行思考（下文会有详细的说明）
对边界收缩行为进行思考（下文会有详细说明）
退出循环之后考虑是否要对返回值进行校验

解析

首先解释一下最容易解释的第四点，由于排除法只是排除了所有不可能的选项，所以如果在这个有序数组中原本就不存在target排除法依然会返回一个下标，这时候就需要对这个下标进行检验，如果题目已经确保这个数组中存在需要寻找的元素则不需要进行二次检验。

情况分析

1. 在有序数组中查找等于目标元素的第一个索引

在这种情况下首先给出正确的代码，读者可以直接跳过代码阅读解析。

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

可以看到先对左右指针的取值进行定义，在这种情况下右指针指向最后一个数字即可。顺带一笔，这里的mid的求解方法可以防止int越界的发生，在二分查找中推荐使用这种算法来求中值。接下来就是条件的判断如果nums[mid]<target那么我们可以肯定的是我们最终要求的下标一定在mid下标的右侧，所以我们将左指针进行右移，同时我们考虑到我们要求的是第一个索引，所以我们可以将mid下标直接排除。而对于nums[mid]>=target的情况我们可以确定最终要求的下标在mid的左侧，但是并不知道mid是否就是我们需要寻找的下标即不能排除mid，所以将right=mid。

在这里需要提一下，可能会有人有疑问，为什么判断条件不能是nums[mid]<=target，我们寻找的是目标元素的第一个索引，在排除法的思想中，若nums[mid]<target我们可以确定mid及mid的左侧不会出现目标元素的第一个索引，但是如果nums[mid]=target我们会发现是目标元素的第一个索引不可能出现在mid的右侧，这两个条件实际上是冲突的，所以我们将等于的情况与大于合并而不是与小于合并。

2. 在有序数组中查找等于目标元素的最后一个索引

这个情况其实通过以上的分析已经相当容易理解了，我直接给出代码和注释，希望读者能够自行理解

public int findLast(int[] nums, int target){
    int left = 0,right = nums.length - 1;
    while(left<right){
        int mid = ((right - left + 1) >> 1) +left;
        if (nums[mid] > target) //在这种情况下能确定需要求的下标在mid的左侧
            right = mid - 1;
        else //要求的下标在mid及mid的右侧
            left = mid;
    }
    return right;
}

3. 在有序数组中查找第一个大于目标元素的下标

主要就是对判断条件的分析，当nums[mid]>target时需要寻找的下标一定在mid及mid的左侧，而等于和小于则在mid的右侧，下面直接给出代码

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

4. 在有序数组中查找第一个小于目标元素的下标

同理，直接给代码

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