The working principle and code implementation of binary search

Binary search is an efficient algorithm for finding specific elements in an ordered array.

Its basic idea is to compare the target value with the elements in the middle of the array, and narrow the search scope according to the comparison results until the target value is found or it is determined that the target value does not exist in the array.

Below I will explain to you in detail how to write efficient binary search code using a simple ordered array.

First, we need to clarify the premise of binary search: the array must be ordered.

If the array is not ordered, then binary search will not work properly.

Therefore, before using binary search, make sure your array has been sorted in ascending or descending order.

Now, let's take a look at the Python implementation of binary search:

def binary_search(arr, target):
    """
    使用二分搜索在有序数组arr中查找目标值target。

    如果找到目标值，返回其在数组中的索引；否则返回-1。

    """
    left, right = 0, 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

This code defines a code called binary_searchFunction that accepts an ordered array arrAnd a target value targetAs a parameter.

The function returns the index of the target value in the array, or -1 if the target value does not exist in the array.

Let's analyze this code step by step: 1. Initialize two pointers leftSumright, point to the first and last elements of the array, respectively.

2. Enter a loop, when leftLess than or equal to rightContinue to execute.

This means that we still have elements to check.

3. Calculate the intermediate index mid, it is leftSumrightThe average of (rounded down).

4. Check for intermediate elements arr[mid]Is it equal to the target value target。

If yes, we find the target value and return its index.

5. If arr[mid]Less than target, indicating that the target value is to the right of the middle element, so we will leftUpdated to mid + 1, narrow down the search.

6. if arr[mid]More than target, indicating that the target value is on the left side of the middle element, so we will rightUpdated to mid - 1, narrow down the search.

7. If the target value is not found at the end of the loop, returning -1 means that the target value does not exist in the array.

The time complexity of this algorithm is O (log n), where n is the length of the array.

This is because each iteration halves the search scope.

This makes binary search much faster than linear search (checking each element one by one), especially in large arrays.

Now, let's look at a practical example to demonstrate how to use this function:

# 示例数组
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

# 查找目标值
target = 13
index = binary_search(arr, target)

if index != -1:
    print(f"目标值 {target} 在数组中的索引为 {index}")
else:
    print(f"目标值 {target} 不在数组中")

In this example, we look for the target value 13 in an ordered array.

After running the above code, the output will be:

目标值 13 在数组中的索引为 6

This shows that the target value of 13 does exist in the array, and its index is 6.

If we try to find a value that does not exist in the array, such as 20, the output will be:

目标值 20 不在数组中

This is how to write efficient binary search code using a simple ordered array.

I hope this article can help you understand the principle and implementation of binary search.

In practical programming, binary search is a very useful tool, which can significantly improve search efficiency, especially when dealing with large amounts of data.