python中的二进制搜索算法解释_python_weixin

Binary search also known as half-interval search, logarithmic search is an algorithm used in computers to find the position of a value in a sorted array.

二进制搜索也称为半间隔搜索 ， 对数搜索是计算机中用于查找排序数组中值位置的算法。

Bubble sort, Linear search, Quick sort are some of the other type of sorting algorithm available. In this article we are going to learn about the searching algorithm known as Binary search.

冒泡排序，线性搜索，快速排序是可用的其他一些排序算法。在本文中，我们将学习称为二进制搜索的搜索算法。

Binary search is little bit more advanced and have more accurate results when compared with linear search and bubble sort algorithms.

与线性搜索和气泡排序算法相比，二进制搜索稍微先进一些，并且结果更准确。

So let’s assume that you have a list with 10000 items in it. The item you are looking for is in the 9000th place. If you implement the linear search algorithm in this scenario it will take much time to give you the result. Because the algorithm needs check each and every item in the list.

因此，假设您有一个包含10000个项目的列表。您正在寻找的项目在第9000位。如果在这种情况下实现线性搜索算法，将需要很多时间才能得到结果。因为该算法需要检查列表中的每个项目。

So how can we write our code to show the result quickly? Here’s how….

那么我们如何编写代码以快速显示结果呢？这是如何做…。

We have a list with the following items.

我们有一个包含以下项目的列表。

So first we need to specify the Lower bound (L) and Upper bound (U). Lower bound is the first index of the list and upper bound is the last index of the list.

因此，首先我们需要指定下限(L)和上限(U)。下限是列表的第一个索引，上限是列表的最后一个索引。

Once you finish assigning these bounds you have to find a mix index (M).

完成分配这些边界后，您必须找到一个混合索引(M)。

So what is mid index? As name implies it is the middle position between lower and upper bounds. So we can say that,

那么什么是中指？顾名思义，它是上下限之间的中间位置。所以我们可以这样说

Mid Index = (Lower bound + Upper bound)/2

中索引=(下限+上限)/ 2

In my case, Mid Index = (0 + 13)/2 = 6

就我而言，中指=(0 + 13)/ 2 = 6

In here we are doing integer division not float division. Therefore 13/2 = 6 not 6.5.

在这里，我们正在执行整数除法而不是浮点除法。因此13/2 = 6而不是6.5。

Now let’s specify the item that we need to find from our list. Let’s say we need to find number “90” from our list.

现在，让我们指定我们需要从列表中查找的项目。假设我们需要从列表中找到数字“ 90”。

OK now the mid value we got is 6. The value of index 6 in our list is 10.

现在，我们得到的中间值为6。列表中索引6的值为10。

Now we have to check whether if mid value is matching the item that we are searching. (10 ≠90) Since they are not matching we need to change the lower bound or the upper bound. How do we know which one to change? Here’s how…

现在，我们必须检查中间值是否与我们要搜索的项目匹配。 (10≠90)由于它们不匹配，我们需要更改下限或上限。我们如何知道要更改哪一个？这是如何做…

You have to check the value you are searching for is smaller or bigger than the mid value. If the value is smaller change upper bound and mid value becomes the new upper bound. If value is greater change lower bound and mid value becomes new lower bound.

您必须检查要搜索的值是小于还是大于中间值。如果该值较小，则更改上限，中值变为新的上限。如果值更大，则更改下界，中间值变为新的下界。

So in my case the search value is bigger there for I need to change my lower bound and the mid value (10) becomes my new lower bound.

因此，在我的情况下，搜索值更大，因为我需要更改下界，而中间值(10)成为我的新下界。

Now we got a new lower bound (10) and the upper bound (1000) values. Now we can again find a mid-value.

现在我们得到了一个新的下限(10)和上限(1000)。现在，我们可以再次找到中间值。

Mid Index = (Lower bound + Upper bound)/2 = (6 + 13)/2 = 9

中索引=(下限+上限)/ 2 =(6 + 13)/ 2 = 9

Now once again we can check if mid value is matching the item that we are searching. So according to my case they are matching. Which means we found our item from the list.

现在，我们可以再次检查中间值是否与我们要搜索的项目匹配。因此，根据我的情况，它们是匹配的。这意味着我们从列表中找到了我们的物品。

That’s how you do the binary search. If you have huge list this method will be a lifesaver. There is one main drawback in this search method. You need to have a sorted list if you want search your list using binary search.

这就是您执行二进制搜索的方式。如果您的清单很大，那么此方法将是您的救星。这种搜索方法有一个主要缺点。如果要使用二进制搜索来搜索列表，则需要具有排序列表。

Since we have talked all about the logic behind binary search now let’s implement this logic into python code.

既然我们已经讨论了二进制搜索背后的逻辑，现在让我们在python代码中实现此逻辑。

def search(list, n):
    l = 0
    u = len(list)-1
    while 1 <= u:
        mid = (l+u) // 2
        if list[mid] == n:
            return True
        else:
            if list[mid] < n:
                l = mid+1
            else:
                u = mid-1
    return False
list = [1,3,4,7,8,9,10,45,50,90,100,150,600,1000]
n = 90
if search(list, n ):
    print("Found")
else:
    print("Not Found")