这个程序是如何工作的？firstGreaterEqual方法怎么样

Question

我是个新手。我希望这个问题符合指导方针。 谢谢你。！你知道吗

     class Solution:
        def searchRange(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            start = self.firstGreaterEqual(nums, target)
            if start==len(nums) or nums[start]!=target:
                return [-1, -1]
            return [start, self.firstGreaterEqual(nums, target+1)-1]
        def firstGreaterEqual(self, nums, target):
            lo, hi = 0, len(nums)
            while lo<hi:
                mid = (hi+lo)//2
                if nums[mid]<target:
                    lo = mid + 1
                else:
                    hi = mid
            return lo


    Input: nums = [5,7,7,8,8,10], target = 6
    Output: [-1,-1]

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

这个程序是搜索一个范围 link to the program 此解决方案具有最佳运行时间。 我发现很难理解背后的逻辑。 它是使用二进制搜索，但我不完全理解它。你知道吗

Answer 1

所以它基本上是按照你指出的二进制搜索原理工作的。你知道吗

下面是简单的算法分解

• 首先你要找到你要寻找的目标的第一个出现点
  • 如果目标不存在，则返回[-1，-1]

• 然后找到target+1的第一个出现项，假设出现项存储在变量end中，那么原始target的最后一个出现项将是'end-1'

  首先，您会找到您要查找的目标的第一个出现点
  示例数组nums = [5,7,7,8,8,10], target = 8

• lo = 0，hi = len(nums)，mid = (hi+lo)//2

• 现在搜索数组的中间，在这里mid = 3
• nums[3]处的元素是8，这与taget相同
• 这是起始索引，返回它并存储在值start

既然我们得到了第一次出现，我们就进入下一个阶段

然后找到target+1

1. lo = 0，hi = len(nums)，mid = (hi+lo)//2，target+1 = 9
2. 现在搜索数组的中间，在这里mid = 3
3. nums[3]处的元素是8，小于target+1，所以我们设置low = mid +1
4. 接下来我们设置mid = (hi+lo)//2，即5
5. nums[5]处的元素是10，大于target+1，所以我们设置hi = mid
6. 在上一步之后，我们将退出while loop，因为条件while lo<hi的计算结果为False
7. 返回lo作为结束索引

现在我们有start=3，end=5，所以我们返回[start，end-1]，即[3，4]

参考文献：

• GeeksForGeeks blog post for same problem