The working principle and code implementation of binary search

In computer science, Binary Search is an efficient search algorithm for arrays that have been sorted.

It quickly locates the target value by repeatedly halving the search range.

This article will explain in detail how binary search works and provide a simple and easy-to-understand code implementation.

How binary search works.

The basic idea of binary search is: in an ordered array, compare the target value with the size of the middle element each time, so as to determine whether the next step is to continue the search in the left half or the right half.

The specific steps are as follows: 1. # Initialization #: Set two pointers, leftSumright, point to the start and end positions of the array, respectively.

2. # Calculate the middle position #: Calculate the middle position of the current search range mid = (left + right) / 2。

3. # Compare the middle element with the target value #: -If the intermediate element is equal to the target value, the search is successful and the index of the element is returned.

-If the middle element is greater than the target value, the target value must be in the left half, update right = mid - 1。

-If the middle element is less than the target value, the target value must be in the right half, update left = mid + 1。

4. # Repeat the above step # until the target value is found or the search range is empty (i.e left > right）。

Code implementation.

Below is an example of a simple binary search code written in Python:

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  # 未找到目标值，返回 -1

# 测试代码
if __name__ == "__main__":
    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    target = 7
    result = binary_search(arr, target)
    
    if result != -1:
        print(f"目标值 {target} 在数组中的索引为 {result}")
    else:
        print(f"目标值 {target} 不在数组中")

Code annotation parsing.

1. # Function Definition #: binary_search(arr, target)Accept an ordered array arrAnd a target value target。

2. # Initialization pointer #: leftSumrightPoint to the start and end positions of the array, respectively.

3. # Cycle Condition #: while left <= rightMake sure the search scope is valid.

4. # Calculate the middle position #: mid = (left + right) // 2Use the Divide Operator //Calculate the middle position.

5. # Compare the middle element with the target value #: - if arr[mid] == target, return mid。

- if arr[mid] < target, indicating that the target value is in the right half, update left = mid + 1。

- if arr[mid] > target, indicating that the target value is in the left half, update right = mid - 1。

6. # Return result #: If the target value is not found after the loop ends, return -1。

Practical application scenarios.

Binary search is widely used in various scenarios that require efficient search, such as: - # Database Query #: Quickly find records in sorted data tables.

- # File System #: Quickly locate files in the sorted file list.

- # Search Engine #: Quickly locate keywords in sorted indexes.

- # Financial Application #: Quickly find specific price points in the sorted price list.

Summarize.

Binary search is a very efficient search algorithm, especially suitable for large-scale ordered data search.

By understanding its working principle and mastering its code implementation, we can flexibly use this algorithm in actual development to improve the performance and efficiency of the program.

I hope this article can help you better understand and apply the binary search algorithm.