How to use Python to implement binary search

First, create a function named binary_search: pass two parameters, the list of elements and the value to be found.

def binary_search(_list, value):

Next, define the required variables inside the function. The key to the dichotomy is to search from the middle of the list to both sides (the expression may not be rigorous, but this is probably the meaning), so for the sake of intuition, define left , right and mid are three variables, representing respectively: the starting index, the ending index and the middle index of the list.

    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

The next step is to implement the key part of binary search. First define a while loop so that the search can proceed smoothly. The if branch statement is nested within the while function to implement conditional judgment. There are three situations:

1. _list[mid] == value: The middle value happens to be the value we need to find, so just return the corresponding index directly.

2. _list[mid] > value: The value to be found is on the left side of mid. Update the value of right to mid to narrow the search range.

3._list[mid] < value: The value to be found is on the right side of mid, update the value of left to mid, and search on the right side of mid.

Finally, update the value of mid to start the next round of search. At the same time, use the while-else statement to judge the situation where it is not found, and give a return value.

    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1

Finally, the complete code and test running performance are as follows:

""" a demo realize binary search"""
 
 
def binary_search(_list, value):
    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1
 
 
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

Running results:

When there is no value to be found ：

##

The above is the detailed content of How to use Python to implement binary search. For more information, please follow other related articles on the PHP Chinese website!