LeetCode搜索范围题解中do-while循环的Big O复杂度分析

核心结论 #

你的解法在最坏情况（数组全为目标值）下的时间复杂度是O(N)，不符合题目要求的O(logn)。

复杂度拆解 #

1. 外层二分查找：确实是O(logn)，最多执行log₂n次迭代就能定位到目标值。
2. 内部do-while循环：当数组全是target时，这个循环会从找到的中间位置向左右遍历整个数组——左边从m-1一直遍历到数组开头，右边从m+1遍历到数组末尾，总共会执行O(N)次操作。
3. 整体复杂度：因为外层二分找到目标后就直接进入内部循环并返回结果，不会再回到外层循环，所以整体复杂度是O(logn + N)，等价于O(N)，不是你担心的O(NlogN)。

你的代码 #

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0,m,h = nums.size()-1;
        vector<int> ans;
        ans.push_back(-1);
        ans.push_back(-1);

        while (l <= h) {
            m = (l+h)/2;
            if (nums[m] == target) {
                l = m-1;
                h = m+1;
                ans.at(0)=m;
                ans.at(1)=m;
                do {
                    if (l >= 0 and nums[l] == target) {
                        ans.at(0)=l;
                        l--;
                    }
                    else {
                        l = -99;
                    }
                    if (h <= nums.size()-1 and nums[h] == target) {
                        ans.at(1)=h;
                        h++;
                    }
                    else {
                        h = nums.size();
                    }
                } while (l >= 0 or h < nums.size());
                return ans;
            }
            else if (nums[m] < target) {
                l = m+1;
            }
            else {
                h = m-1;
            }
        }
        return ans;

    }
};

符合O(logn)要求的改进思路 #

要达到题目要求的时间复杂度，应该用两次二分查找分别定位左边界和右边界：

• 第一次二分：找第一个等于target的位置（左边界），即使找到target也继续向左缩小范围。
• 第二次二分：找最后一个等于target的位置（右边界），即使找到target也继续向右缩小范围。

示例代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = findLeft(nums, target);
        if (left == -1) return {-1, -1};
        int right = findRight(nums, target);
        return {left, right};
    }

private:
    int findLeft(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int res = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                res = mid;
                r = mid - 1; // 继续向左找更靠左的边界
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }

    int findRight(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        int res = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                res = mid;
                l = mid + 1; // 继续向右找更靠右的边界
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return res;
    }
};

这种解法两次二分都是O(logn)，整体复杂度保持O(logn)，完全符合题目要求。

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