Python 列表中的二分查找 [英] Binary search in a Python list

问题描述

我正在尝试对 Python 中的列表执行二进制搜索.列表是使用命令行参数创建的.用户输入他想在数组中查找的数字，然后返回元素的索引.出于某种原因，程序只输出 1 和 None.代码如下.非常感谢任何帮助.

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.

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$ 

推荐答案

好吧，您的代码中有一些小错误.要找到它们，您应该使用调试器，或者至少添加跟踪以了解发生了什么.这是带有使问题不言自明的痕迹的原始代码:

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
  ...

您可以立即看到:

• 你在一个子数组中搜索，当你低于avg
时，它会跳过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

这还不是全部，当您以 min == max 结束循环时，您不会返回任何内容(意味着您返回 None).最后但并非最不重要的是切勿将标准 Python 库中的名称用于您自己的变量.

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 never use a name from the standard Python library for your own variables.

这里是固定代码:

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

这篇关于Python 列表中的二分查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！