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

Question

我是堆栈溢出的新手。我希望这个问题符合指导方针。 Thnakyou.!

     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

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

这里是简单分解的算法

首先你找到你正在寻找的目标的第一次出现
- 如果目标没有出现，return [-1, -1]
然后找到第一个出现的target+1，假设这个出现存储在变量end中，那么原来target的最后一个出现就是`结束-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相同
这是起始索引，return 它存储在值 start

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

然后找到第一个出现的target+1

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

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

参考：

GeeksForGeeks blog post for same problem

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

How does this program work? How's firstGreaterEqual method working

python

search

binary-search