How to implement binary search algorithm using Python?

How to use Python to implement the binary search algorithm?

The binary search algorithm, also known as the binary search algorithm, is an efficient search algorithm. It works on ordered arrays or lists, narrowing down the search by comparing the target value to elements in the middle of the array. The following will introduce how to implement the binary search algorithm in Python and provide specific code examples.

1. Algorithm idea:
2. Compare the target value with the element in the middle of the array;
3. If they are equal, return the element position;
4. If the target value is greater than the element in the middle, continue searching in the right half;
5. If the target value is smaller than the element in the middle, continue searching in the left half;
6. Continuously expand the search range Zoom in half until the target value is found or the search range is empty.
7. Code implementation:
   The following is a code example using Python to implement the binary search algorithm:

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

3. Usage example:
   Next we use an ordered array to perform the actual search operation. Suppose there is an array arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] arranged in ascending order, and we want to find the position of the number 10.

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 10

result = binary_search(arr, target)

if result != -1:
    print("目标值在数组中的位置是：", result)
else:
    print("数组中不存在目标值。")

After the above code is run, the output result is: "The position of the target value in the array is: 9".

4. Summary:
   Through the introduction of this article, we have learned how to use Python to implement the binary search algorithm. This algorithm has high efficiency in searching for target values ​​in ordered arrays or lists, and can greatly improve the speed of searching. In practical applications, we can appropriately optimize the binary search algorithm as needed to meet the needs of more scenarios. At the same time, we can also use recursive methods to implement the binary search algorithm, but be careful to avoid stack overflow problems.

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