python中的左二进制搜索
python中的左二进制搜索
提问于 2014-03-07 13:04:21
例如，如果输入是1,2, 3，3 ,4,4,5，而我搜索3，它应该返回2，因为索引2是3的最左边的出现。
在1, 1，1,1,1,1,1,1，1，1中，我搜索1，你应该返回0。
我们如何编写函数来在二进制搜索中遍历返回？
回答 2
Stack Overflow用户
发布于 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")Stack Overflow用户
发布于 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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22241912
复制相关文章
相似问题