Python 列表中的二分查找
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/38346013/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Binary search in a Python list
提问by Anuvrat Tiku
I am trying to perform a binary search on a list in python. List is created using command line arguments. User inputs the number he wants to look for in the array and he is returned the index of the element. For some reason, the program only outputs 1 and None. Code is below. Any help is extremely appreciated.
我正在尝试对 python 中的列表执行二进制搜索。列表是使用命令行参数创建的。用户输入他想在数组中查找的数字，然后返回元素的索引。出于某种原因，程序只输出 1 和 None。代码如下。非常感谢任何帮助。
import sys
def search(list, target):
min = 0
max = len(list)-1
avg = (min+max)/2
while (min < max):
if (list[avg] == target):
return avg
elif (list[avg] < target):
return search(list[avg+1:], target)
else:
return search(list[:avg-1], target)
print "The location of the number in the array is", avg
# The command line argument will create a list of strings
# This list cannot be used for numeric comparisions
# This list has to be converted into a list of ints
def main():
number = input("Please enter a number you want to search in the array !")
index = int(number)
list = []
for x in sys.argv[1:]:
list.append(int(x))
print "The list to search from", list
print(search(list, index))
if __name__ == '__main__':
main()
CL :
Anuvrats-MacBook-Air:Python anuvrattiku$ python binary_search.py 1 3 4 6 8 9 12 14 16 17 27 33 45 51 53 63 69 70
Please enter a number you want to search in the array !69
The list to search from [1, 3, 4, 6, 8, 9, 12, 14, 16, 17, 27, 33, 45, 51, 53, 63, 69, 70]
0
Anuvrats-MacBook-Air:Python anuvrattiku$
回答by tuergeist
In Python2 and Python3 you can use bisectas written in the comments. Replace your search with the following
在 Python2 和 Python3 中，您可以使用注释中所写的bisect。将您的搜索替换为以下内容
from bisect import bisect_left
def search(alist, item):
'Locate the leftmost value exactly equal to item'
i = bisect_left(alist, item)
if i != len(alist) and alist[i] == item:
return i
raise ValueError
alist = [1,2,7,8,234,5,9,45,65,34,23,12]
x = 5
alist.sort() # bisect only works on sorted lists
print(search(a, x)) # prints 2 as 5 is on position 2 in the sorted list
Also, the AS SortedCollection (Python recipe)could be useful.
此外，AS SortedCollection（Python 配方）可能很有用。
The following code (from here) performs the binary search and returns position and if the item was found at all.
以下代码（来自此处）执行二进制搜索并返回位置以及是否找到了该项目。
def binarySearch(alist, item):
first = 0
last = len(alist)-1
found = False
while first<=last and not found:
pos = 0
midpoint = (first + last)//2
if alist[midpoint] == item:
pos = midpoint
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return (pos, found)
Will return (2, True)if used in the example above.
(2, True)如果在上面的示例中使用将返回。
回答by Serge Ballesta
Well, there are some little mistakes in your code. To find them, you should either use a debugger, or at least add traces to understand what happens. Here is your original code with traces that make the problems self evident:
好吧，您的代码中有一些小错误。要找到它们，您应该使用调试器，或者至少添加跟踪以了解发生了什么。这是带有使问题不言自明的痕迹的原始代码：
def search(list, target):
min = 0
max = len(list)-1
avg = (min+max)/2
print list, target, avg
...
You can immediately see that:
您可以立即看到：
- you search in a sub array that skips
avg-1when you are belowavg - as you search in a sub array you will get the index in that subarray
- 您在低于平均水平
avg-1时跳过的子数组中搜索 - 当你在一个子阵列搜索，你会得到该指数在子阵
The fixes are now trivial:
修复现在是微不足道的：
elif (list[avg] < target):
return avg + 1 + search(list[avg+1:], target) # add the offset
else:
return search(list[:avg], target) # sublist ends below the upper limit
That's not all, when you end the loop with min == max, you do not return anything (meaning you return None). And last but not least neveruse a name from the standard Python library for your own variables.
这还不是全部，当您以 结束循环时min == max，您不会返回任何内容（意味着您返回 None）。最后但并非最不重要的是，永远不要将标准 Python 库中的名称用于您自己的变量。
So here is the fixed code:
所以这里是固定代码：
def search(lst, target):
min = 0
max = len(lst)-1
avg = (min+max)/2
# uncomment next line for traces
# print lst, target, avg
while (min < max):
if (lst[avg] == target):
return avg
elif (lst[avg] < target):
return avg + 1 + search(lst[avg+1:], target)
else:
return search(lst[:avg], target)
# avg may be a partial offset so no need to print it here
# print "The location of the number in the array is", avg
return avg
回答by Attaque
@Serge Ballesta 's solution is undoubtly the correct answer to this question.
@Serge Ballesta 的解决方案无疑是这个问题的正确答案。
I am just going to add another way of solving this:
我只是要添加另一种方法来解决这个问题：
def search(arr, item, start, end):
if end-start == 1:
if arr[start] == item:
return start
else:
return -1;
halfWay = int( (end-start) / 2)
if arr[start+halfWay] > item:
return search(arr, item, start, end-halfWay)
else:
return search(arr, item, start+halfWay, end)
def binarysearch(arr, item):
return search(arr, item, 0, len(arr))
arr = [1, 3, 4, 6, 8, 9, 12, 14, 16, 17, 27, 33, 45, 51, 53, 63, 69, 70]
print("Index of 69: " + str(binarysearch(arr, 69))) # Outputs: 16
回答by Kevin
The reason you aren't getting correct result is because in every recursive call your code is sending sliced array. So the array length keeps reducing. Ideally you should work out a way to send original array and work with only start, end indices.
您没有得到正确结果的原因是因为在每次递归调用中，您的代码都在发送切片数组。所以数组长度不断减少。理想情况下，您应该想出一种方法来发送原始数组并仅使用开始、结束索引。
