例如,如果输入是1,2, 3,3 ,4,4,5,而我搜索3,它应该返回2,因为索引2是3的最左边的出现。
在1, 1,1,1,1,1,1,1,1,1中,我搜索1,你应该返回0。
我们如何编写函数来在二进制搜索中遍历返回?
发布于 2018-07-30 00:29:17
您可以使用以下代码在左二分查找中查找最左边的元素
def left_binary_search(input, value):
try:
if (type(input).__name__ != 'list') or (type(value).__name__ != 'int'):
raise TypeError
low = 0
high = len(input) - 1
check = (low + high) // 2
q = False
l1 = []
while low <= high:
mid = (low + high) // 2
if input[mid] > value:
high = mid - 1
elif input[mid] < value:
low = mid + 1
else:
if mid > check:
return -1
else:
q = True
l1.append(mid)
high = mid
if low == high:
return min(l1)
if q == False:
return -1
return min(l1)
except TypeError:
print("invalid type")
发布于 2019-07-28 10:43:18
此函数返回元素的最左侧索引,如果未找到元素,则返回-1。
def left_binary_search(arr, value):
low = 0
high = len(arr) - 1
index = -1
while (low <= high):
mid = (low + high) // 2
if arr[mid] == value:
index = mid
high = mid - 1
elif arr[mid] < value:
low = mid + 1
else:
high = mid - 1
return index
https://stackoverflow.com/questions/22241912
复制相似问题