O(log n)查找有序数组目标值首尾索引的二分代码复杂度问询

我求解了一道LeetCode题目，题目要求如下：
给定按非递减顺序排序的整数数组nums，查找给定目标值target在数组中的起始和结束位置。
如果数组中未找到目标值，返回[-1, -1]。
要求编写的算法时间复杂度必须为O(log n)。

示例 #

示例1 #

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

示例2 #

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

示例3 #

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

约束条件 #

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums为非递减数组
• -10^9 <= target <= 10^9

我用二分查找的思路写了解法，提交后运行耗时6ms，但不确定是否满足O(log n)的时间复杂度要求，代码如下：

public static int[] returnIndices = new int[2];
    
    public int[] searchRange(int[] nums, int target) {
        int[] resultArr = new int[2];

        if(nums.length == 0 && target == 0) {
            resultArr[0] = -1;
            resultArr[1] = -1;
            System.out.print(resultArr[0] + "," + resultArr[1]);
            return resultArr;
        }

        binarySearch(nums, target);
        resultArr = getIndexOf();

        System.out.print(resultArr[0] + "," + resultArr[1]);
        return resultArr;
    }
    
    public int[] getIndexOf() {
        return returnIndices;
    }

    public int[] setIndex(int index) {
        if(index == -1) {
            returnIndices[0] = -1;
            returnIndices[1] = -1;
        }
        else {
            int lastIndex = index + 1;
            returnIndices[0] = index;
            returnIndices[1] = lastIndex;
        }

        return returnIndices;
    }

    public int binarySearch(int[] nums, int target) {
        int low = 0;
        int high = nums.length;
        int mid = 0;

        while(low <= high) {
            mid = low+high/2;

            if(nums[mid] == target) {
                setIndex(mid);
                return mid;
            }
            if(nums[mid] < target) {
                low = mid+1;
            }
            if(nums[mid] > target) {
                high = mid-1;
            }
         }

        setIndex(-1);
        return -1;
    }

你的代码连题目正确性要求都满足不了，更谈不上复杂度达标，问题主要有几类：

1. 核心逻辑完全错误
   你只要在二分里找到任意一个等于target的位置，就直接把起始位置设为当前下标、结束位置设为下标+1，这和题目要求差得远。比如数组是[8,8,8,8]，target=8，不管你二分命中哪个位置，返回的结果都不可能是正确的[0,3]，如果命中的是最后一个8，结束位置会直接指向非target值，结果完全错误。
   另外你写的空数组判断逻辑毫无意义：只有空数组且target为0的时候才返回[-1,-1]，空数组传其他target的时候，代码会直接走到二分逻辑，访问数组成员直接越界。
2. 二分实现本身有bug
   首先mid计算写错了，运算符优先级问题导致low+high/2实际算的是low + (high/2)，正确写法是low + (high - low)/2，不仅算出来的mid不对，还会出现下标越界。其次你把high初始化为nums.length，循环条件又是low <= high，当low追平high到数组长度位置时，访问nums[mid]必然越界。
   还有你用了静态数组存返回值，在线判题系统是连续跑测试用例的，上一个用例的结果会残留在静态变量里，直接污染后续用例的返回结果。
3. 复杂度相关问题
   单看你写的二分查找流程，如果修正mid和边界的bug，找单个匹配点的过程确实是O(log n)，但题目要求找起止两个边界，正确做法是做两次二分：一次找第一个等于target的位置，一次找最后一个等于target的位置，两次二分整体还是O(log n)复杂度。你现在的代码根本没做边界查找，本质是没完成题目要求，不是复杂度够不够的问题。

符合要求的参考实现 #

public int[] searchRange(int[] nums, int target) {
    int leftBound = findFirstMatch(nums, target);
    int rightBound = findLastMatch(nums, target);
    return new int[]{leftBound, rightBound};
}

private int findFirstMatch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    int res = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            res = mid;
            high = mid - 1; // 匹配到后继续往左搜更早的匹配项
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

private int findLastMatch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    int res = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) {
            res = mid;
            low = mid + 1; // 匹配到后继续往右搜更晚的匹配项
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

这个实现没有线性遍历操作，两次二分查找的时间复杂度都是O(log n)，加起来还是O(log n)，完全符合题目要求，也不会出现越界、结果错误、变量污染的问题。

内容的提问来源于stack exchange，提问作者nmahesh