在Python列表中进行二进制搜索

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了在Python列表中进行二进制搜索，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2383字，纯文字阅读大概需要4分钟。

内容图文

我试图在python中的列表上执行二进制搜索. List是使用命令行参数创建的.用户输入他想要在数组中查找的数字,并返回元素的索引.由于某种原因,程序只输出1和无.代码如下.
非常感谢任何帮助.

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$

解决方法:

好吧,你的代码中有一些小错误.要找到它们,您应该使用调试器,或者至少添加跟踪以了解发生的情况.这是您的原始代码,其中包含使问题显而易见的痕迹：

def search(list, target):
  min = 0
  max = len(list)-1
  avg = (min+max)/2
  print list, target, avg
  ...

你可以立即看到：

>你搜索一个子阵列,当你低于平均值时跳过avg-1
>当您在子数组中搜索时,您将获得该子数组中的索引

修复现在是微不足道的：

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库中的名称来表示您自己的变量.

所以这是固定代码：

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列表中进行二进制搜索全部内容，希望文章能够帮你解决在Python列表中进行二进制搜索所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端