我正在学习有关Leetcode的Binary Search模板II。 https://leetcode.com/explore/learn/card/binary-search/126/template-ii/937/
def binarySearch(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if len(nums) == 0:
return -1
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid
# Post-processing:
# End Condition: left == right
if left != len(nums) and nums[left] == target:
return left
return -1
据说该模板的关键属性包括
我不理解代码“访问元素的直接右邻居”如何使用它或“确定条件是否满足并决定向左还是向右走”。
如何运作？
我认为您是对的，您引用的“关键属性”是胡说八道。
有趣的是，谦虚的二进制印章比看起来更微妙。
...在循环的顶部，right是仍要考虑的最后一个元素的索引+ 1。因此，初始right为len(nums)。当left == right并且还有no个元素需要考虑时，循环退出。
查看当我们减少到5个元素时会发生什么，我们可能有left，mid和right索引以及它们引用的nums[]片段：
left=26: v0 <= test | left=11: v0 <= test
27: v1 <= test | 12: v1 <= test
mid=28: test # mid=(26+31)//2 | mid=13: test # mid=(11+16)//2
29: v3 >= test | 14: v3 >= test
30: v4 >= test | 15: v4 >= test
right=31: xxxx | right=16: xxxx
if test < target -- left = mid+1
left=29: v3 | left=14: v3
30: v4 | 15: v4
right=31: xxxx | right=16: xxxx
if test > target -- right = mid
left=26: v0 | left=11: v0
27: v1 | 12: v1
right=28: xxxx | right=13: xxxx
剩下2个要考虑的元素和left < right。 （为避免疑问，这显示了两种情况，一种情况为left偶数，另一种情况为奇数。）
当我们减少到4个元素时，我们可能会：
left=27: v0 <= test | left=12: v0 <= test
28: v1 <= test | 13: v1 <= test
mid=29: test # mid=(27+31)//2 | mid=14: test # mid=(12+16)//2
30: v3 >= test | 15: v3 >= test
right=31: xxxx | right=16: xxxx
if test < target -- left = mid+1
left=30: v3 | left=15: v3
right=31: xxxx | right=16: xxxx
if test > target -- right = mid
left=27: v0 | left=12: v0
28: v1 | 13: v1
right=29: xxxx | right=14: xxxx
[剩下1或2个剩余元素要考虑，left < right。
[请注意，在这种情况下，结果是不平衡的，test值为中间对的右手值...这可能与“需要访问元素的直接右邻居”“键有关属性”。
剩下3个元素，我们可能会有：
left=27: v0 <= test | left=12: v0 <= test
mid=28: test # mid=(27+30)//2 | mid=13: test # mid=(12+15)//2
29: v2 >= test | 14: v2 >= test
right=30: xxxx | right=15: xxxx
if test < target -- left = mid+1
left=29: v2 | left=14: v2
right=30: xxxx | right=15: xxxx
if test > target -- right = mid
left=27: v0 | left=12: v0
right=28: xxxx | right=13: xxxx
剩下要考虑的剩余元素和left < right。
[剩余2个元素：
left=27: v0 <= test | left=12: v0 <= test
mid=28: test # mid=(27+29)//2 | mid=13: test # mid=(12+14)//2
right=29: xxxx | right=14: xxxx
if test < target -- left = mid+1
left=29: xxxx | left=14: xxxx
right=left | right=left
if test > target -- right = mid
left=27: v0 | left=12: v0
right=28: xxxx | right=13: xxxx
剩下要考虑的0或1个元素和left <= right。
剩余1个元素：
left= | left=
mid=27: test # mid=(27+28)//2 | mid=12: test # mid=(12+13)//2
right=28: xxxx | right=13: xxxx
if test < target -- left = mid+1
left=28: xxxx | left=13: xxxx
right=left | right=left
if test > target -- right = mid
left=27: xxxx | left=12: xxxx
right=left | right=left
剩余要考虑的0个元素和left == right。
所以，实际上
给定的循环not“保证搜索空间的每一步至少为2”。
和：：
# Post-processing:
# End Condition: left == right
if left != len(nums) and nums[left] == target:
return left
是完全多余的！
left, right = 0, len(nums) - 1 # right = index of last element
while left < right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1 # step past value < target
else:
right = mid - 1 # step past value > target
并且在这种情况下，循环does在要考虑的元素少于2个时退出。
剩余5个元素：
left=26: v0 <= test | left=11: v0 <= test
27: v1 <= test | 12: v1 <= test
mid=28: test # mid=(26+30)//2 | mid=13: test # mid=(11+15)//2
29: v3 >= test | 14: v3 >= test
right=30: v4 >= test | right=15: v4 >= test
if test < target -- left = mid+1
left=29: v3 | left=14: v3
right=30: v4 | right=15: v4
if test > target -- right = mid-1
left=26: v0 | left=11: v0
right=27: v1 | right=12: v1
剩下2个要考虑的要素和left < right。
剩余4个元素：
left=27: v0 <= test | left=12: v0 <= test
mid=28: test # mid=(27+30)//2 | mid=13: test # mid=(12+15)//2
29: v2 | 14: v2
right=30: v3 | right=15: v3
if test < target -- left = mid+1
left=29: v2 | left=14: v2
right=30: v3 | right=15: v3
if test > target -- right = mid-1
left=27: v0 | left=12: v0
right=left | right=left
[剩下1或2个剩余元素要考虑，left <= right。 [请注意，这在与原始代码相反的方向上是不平衡的。]
剩下3个元素：
left=27: v0 <= test | left=12: v0 <= test
mid=28: test # mid=(27+29)//2 | mid=13: test # mid=(12+14)//2
right=29: v2 >= test | right=14: v2 >= test
if test < target -- left = mid+1
left=29: v2 | left=14: v2
right=left | right=left
if test > target -- right = mid-1
left=27: v0 | left=12: v0
right=left | right=left
剩下要考虑的剩余元素和left == right。
[剩余2个元素：
left= | left=
mid=27: test # mid=(27+28)//2 | mid=12: test # (12+13)//2
right=28: v1 >= test | right=13: v1 >= test
if test < target -- left = mid+1
left=28: v1 | left=13: v1
right=left | right=left
if test > target -- right = mid-1
left=27: xxxx | left=12: xxxx
right=left-1 | right=left-1
剩下要考虑的0或1个元素和left >= right。
如果left >= right，则退出循环，如果left == right，则需要考虑一个元素。
您可以设置mid = (left + right + 1) // 2，这会导致偶数个元素在相反（原始）方向上不平衡。
如果是nums[0] > target，则循环可以以left == 0和right == -1退出-但这不是python的问题。
您将会发现，实际上没有必要检查len(nums) > 0。
因此，关于二元排骨的有趣事情是最后发生的事情。
是否值得一路磨到剩余0或1个元素，还是值得更早停止并手动处理最后2、3或4个问题，尚待解决。
您当然可以按照以下方式运行循环：
left, right = 0, len(nums) - 1 # right = index of last element
while 1:
mid = (left + right) // 2
if mid <= left:
# deal with cases of 0, 1 or 2 elements left (0 iff nums[] is empty)
....
使用python -1 // 2给出-1，因此right == -1大小写（对于空的nums[]）不应该使您绊倒。