SoFunction
Updated on 2024-11-17

Python elegant implementation of binary lookup example details

Bisection is an efficient search algorithm for finding a specific element in an ordered array. The idea is to gradually reduce the search range by half until the target element is found or it is determined that the target element does not exist. In this article, we will introduce the basic principles of bisection search and explain it in detail through Python code.

I. Principles

The principle of binary lookup is very simple and the basic steps are as follows:

1. Determine the start point and end point of the search range. Typically, the starting point is the first element of the array and the end point is the last element of the array.

2. Calculate the position of the midpoint and obtain the value of the midpoint.

3. Compare the value at the midpoint with the target value.

  • If the value of the midpoint is equal to the target value, it means that the target element has been found and the lookup is successful.
  • If the value of the midpoint is greater than the target value, it means that the target element may be in the left half, narrowing the lookup to the left half.
  • If the value at the midpoint is less than the target value, it means that the target element may be in the right half, narrowing the lookup to the right half.

4. Repeat steps 2 and 3 until the target element is found or it is determined that the target element does not exist.

II. Sample code

The following is sample code for implementing the binary lookup algorithm using Python:

def binary_search(arr, target):
    """
    Dichotomous lookup algorithm
    :param arr: ordered array
    :param target: target element
    :return: index of the target element, -1 if it does not exist
    """
    low = 0  # The start of the search range
    high = len(arr) - 1  # Find the end of the range

    while low <= high:
        mid = (low + high) // 2  # Calculate the position of the midpoint
        guess = arr[mid]  # Get the value of the midpoint

        if guess == target:  # If the value at the midpoint is equal to the target value, the search is successful
            return mid
        elif guess > target:  # If the value at the midpoint is greater than the target value, it means that the target element is probably in the left half
            high = mid - 1  # Narrow the search to the left half
        else:  # If the value at the midpoint is less than the target value, it means the target element is probably in the right half
            low = mid + 1  # Narrow the search to the right half

    return -1  # Target element does not exist

This code defines a binary_search function that takes an ordered array arr and a target as arguments. The function uses low and high to represent the start and end points of the search range, initially the start point is the first element of the array and the end point is the last element of the array. In each loop, according to the relationship between the value of the middle point and the size of the target value, the start point and end point of the search range are updated in order to gradually narrow the search range. If the target element is found, the index of the target element is returned; if the target element does not exist in the array, -1 is returned.

III. Examples of use

Next, we will use an example to demonstrate the use of binary lookup. Suppose we have an ordered array [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] and we want to find the index of element 11. We can use the binary_search function to do this:

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 11
result = binary_search(arr, target)
if result != -1:
    print("The index of the target element is:", result)
else:
    print("Target element does not exist.")

The output result is:

The index of the target element is: 5

Indicates that the target element 11 exists in the array and has an index of 5.

IV. Summary

Through this article, we understand the basic principles and use of bisection lookup. Dichotomous search is an efficient search algorithm for finding the target element in an ordered array. By gradually reducing the search range by half, the target element can be quickly located. In practice, binary search is often used in searching and sorting.

To this article on the Python elegant implementation of the binary lookup example details of the article is introduced to this, more related Python binary lookup content please search for my previous posts or continue to browse the following related articles I hope that you will support me more in the future!