如何实现二进制搜索? [英] How to implement a binary search?

问题描述

我正在尝试创建一个二进制搜索函数，我尝试使用下面的代码，但是我是python的初学者；我在 i == alist [i] 行上收到错误消息列表索引必须是整数，而不是str".您能帮我解决问题吗?这是整个代码:

  def bsort(alist，i):左= 0右= len(alist)-1我==阿里斯[i][mid] =(左+右)//2如果alist [mid]<一世 :左= [中] + 1elif alis [mid]>一世 :右= [中] + 1elif alist [mid] == i:打印(在...找到单词"，i)Elif左>对:打印(未找到！")i =输入(输入搜索>")alist = [老鼠"，猫"，蝙蝠"，星期六"，"spat"]bsort(alist，i) 

解决方案

因此，从您提出问题的声音出发，您正在尝试使二进制 search 适用于您的示例.首先，知道二进制搜索仅对排序的数据可靠地工作是很有用的.这与标准线性搜索完全不同，后者将始终查找值，而与顺序无关.您可能已经知道二进制搜索是首选，因为二进制搜索每次迭代消除了一半的潜在候选，而线性搜索仅消除了一个元素.话虽如此，让我们讨论我对您的程序所做的修改.首先，进行一些外观上的更改可以大大提高程序的清晰度.

1.)使用描述性变量名非常重要，它可以作为其他人阅读您的代码的注释，以了解变量的内容和功能.这在像python这样的语言中尤其重要，在该语言中，仅通过阅读代码就不容易推断出变量类型.因此，我没有重用变量 i 多次，而是将您的函数参数 target 重命名，因为这是我们尝试查找的搜索词，即目标".我还将您的函数从"bsort"重命名为"bsearch"，因为它可以更准确地描述该函数的作用，这意味着该函数对某些内容进行了排序.

2.)二进制搜索可以使用循环或递归来实现.为简单起见，我选择了使用循环的迭代路线.正如我之前提到的，二进制搜索通过每次迭代消除一半的潜在搜索候选来工作.没有循环，您就消除了一半的候选者(仅一次)，但是除非您非常幸运，否则您可能找不到要搜索的词！相反，您需要继续此过程，直到找到了要搜索的术语.这是 while True:循环的功能.

3.)最后，我们确保使用整数来访问列表的索引.python中的所有列表都从 0到n-1 进行索引，其中 n 是列表中元素的数量.我们无法使用浮点值(例如2.5)访问列表，因为该值不对应于列表中的任何特定插槽".同样，我们不能使用字符串来访问元素，因为列表再次需要一个整数才能执行查找.这是 mid = int((left + right)/2)的目的.

话虽如此，这应该可以达到您的预期目的.我希望这可以帮助你！我也鼓励您看一些如何实现二进制搜索的示例，例如这一个.

  def bsearch(警报，目标):左= 0右= len(alist)-1而True:中= int((左+右)/2)如果alist [mid]<目标 :左=中+ 1elif alist [mid]>目标 :右=中+ 1elif alist [mid] ==目标:打印(在"+ str(mid)处找到单词'" +目标+')休息Elif左>对:打印(未找到！")休息i =输入(输入搜索>")alist = [老鼠"，猫"，蝙蝠"，星期六"，"spat"]alist.sort()bsearch(alist，i) 

I'm trying to create a binary search function, I've attempted it with the code below but am a beginner at python ; I'm getting the error "list indices must be integers, not str" on the line i == alist[i]. Could you please help me fix the problem? Here's the whole code:

def bsort(alist, i):
    left = 0
    right = len(alist)-1
    i == alist[i]

    [mid] = (left + right)//2

    if alist[mid] < i :
        left = [mid] + 1

    elif alis[mid] > i :
        right = [mid] + 1

    elif alist[mid] == i :
        print ("word found at", i )

    elif left > right:
        print ("Not Found!")       


i = input("Enter a search >")
alist = ["rat","cat","bat","sat","spat"]
bsort(alist, i)

解决方案

So from the sound of your question you are attempting to get a binary search working for your example. First, it is useful to know that a binary search only works reliably on sorted data. This is quite different than a standard linear search that will always find the value, regardless of order. As you likely already know binary search is preferred because it eliminates half of the potential candidates per iteration, whereas linear search only eliminates one element. With that said, let's discuss the modifications I have made to your program. First, some cosmetic changes can greatly increase the clarity of your program.

1.) Using descriptive variable names is very important and serves as a note to others reading your code, on what the contents and function of a variable might be. This is especially important in a language like python where variable types are not easily inferred just by reading the code. So instead of reusing the variable i multiple times, I have renamed your function parameter target as that is the search term we are attempting to locate, i.e. our 'target'. I also renamed your function from 'bsort' which implies that the function sorts something, to 'bsearch' which is a more appropriate name because it more accurately describes what the function does.

2.) Binary search can be implemented using a loop or recursion. For simplicity, I have selected the iterative route using a loop. As I mentioned before, binary search works by eliminating half of the potential search candidates each iteration. Without the loop, you do eliminate half of the candidates (only one time), but unless you are extremely lucky you will likely not find the term you are searching for! Instead you need to continue this process until you have located the term you are searching for. This is the function of the while True: loop.

3.) Finally, we have made sure that we are using integers to access the indices of our list. All lists in python are indexed from 0 to n-1 where n is the number of elements in a list. We cannot access a list using a floating point value such as 2.5 because this does not correspond to any specific 'slot' in the list. Similarly, we cannot use a string to access our elements because a list again requires a integer to perform a lookup. This is the purpose of mid = int((left + right)/2).

With all that said, this should work for your intended purpose. I hope this helps you! I also encourage you to take a look at some examples of how to implement a binary search such as this one.

def bsearch(alist, target):
    left = 0
    right = len(alist)-1

    while True:
        mid = int((left + right)/2)
        if alist[mid] < target :
            left = mid + 1
        elif alist[mid] > target :
            right = mid + 1
        elif alist[mid] == target :
            print ("word '" + target + "' found at " + str(mid))
            break
        elif left > right:
            print ("Not Found!")
            break       


i = input("Enter a search >")
alist = ["rat","cat","bat","sat","spat"]
alist.sort()
bsearch(alist, i)

这篇关于如何实现二进制搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！