我阅读了Binary search algorithm - Wikipedia进行二分法搜索重复项的最左侧元素
伪代码：
function binary_search_leftmost(A, n, T):
L := 0
R := n
while L < R:
m := floor((L + R) / 2)
if A[m] < T:
L := m + 1
else:
R := m
return L
用python实现
def search_leftmost(nums: List[int], target: int) -> List[int]:
if len(nums) < 1: return [-1, -1]
lo = 0
hi = len(nums)
logging.debug(f"nums:{list(enumerate(nums))}, target: {target}")
while lo < hi:
mid = (lo+hi) // 2
logging.debug(f"lo:{lo} mid:{mid} hi:{hi}")
if target > nums[lo]:
lo = mid + 1
else:
hi = mid
logging.debug(f"lo: {lo}")
return lo
不幸的是，当用
nums = [5,7,7,8,8,8,8,10]; target = 8测试时$ python 0.bi_search.py
DEBUG nums:[(0, 5), (1, 7), (2, 7), (3, 8), (4, 8), (5, 8), (6, 8), (7, 10)], target: 8
DEBUG lo:0 mid:4 hi:8
DEBUG lo:5 mid:6 hi:8
DEBUG lo:5 mid:5 hi:6
DEBUG lo: 5
它返回5，它既不是最左也不是最右。
我的实现有什么问题？
最佳答案
问题出在执行中。
伪码
if A[m] < T:
L := m + 1
被实现为
if target > nums[lo]: # this should be if nums[mid] < target:
lo = mid + 1
我已经更新了它，并且按预期工作：
def search_leftmost(nums, target):
lo = 0
hi = len(nums)
while lo < hi:
mid = (lo+hi) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
if __name__ == "__main__":
nums = [5,7,7,8,8,8,8,10]
target = 8
assert search_leftmost(nums, target)== 3
nums = [5,7,7,8,8,8,8,10]
target = 7
assert search_leftmost(nums, target) == 1
nums = [5,7,7,8,8,8,8,10]
target = 10
assert search_leftmost(nums, target) == 7
print("Done")
根据Wiki：
即使T不在数组中，L
是T在数组中的排名，还是
数组中小于T的元素。
关于python - 在等分搜索中找到最左边的重复项，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55629841/