C++ 与 Python 中二分查找的实现方法

在编程领域，二分查找是一种高效的查找算法，适用于已排序的数组或列表。下面分别介绍在 C++ 和 Python 中二分查找的实现方法。

在 C++ 中，二分查找通常通过循环来实现。以下是一个简单的示例代码：

#include <iostream>

int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int m = l + (r - l) / 2;

        if (arr[m] == x)
            return m;

        if (arr[m] < x)
            l = m + 1;
        else
            r = m - 1;
    }

    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 23;

    int result = binarySearch(arr, 0, n - 1, x);

    if (result!= -1)
        std::cout << "元素在数组中的索引为: " << result << std::endl;
    else
        std::cout << "数组中未找到该元素" << std::endl;

    return 0;
}

在上述 C++ 代码中，binarySearch 函数接受一个已排序的整数数组 arr 、左右边界 l 和 r 以及要查找的目标值 x 。通过不断比较中间元素与目标值的大小，调整搜索范围，直到找到目标值或确定不存在。

而在 Python 中，二分查找可以通过递归或循环来实现。下面是一个使用循环的实现方式：

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1

    return -1

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23

result = binary_search(arr, x)

if result!= -1:
    print("元素在数组中的索引为:", result)
else:
    print("数组中未找到该元素")

无论是 C++ 还是 Python，二分查找的核心思想都是通过不断缩小搜索范围，快速定位目标元素。这种算法的时间复杂度为 O(log n)，相较于顺序查找的 O(n)，在处理大规模数据时具有明显的优势。

掌握二分查找的实现方法，对于提高程序的效率和性能有着重要的意义。在实际应用中，根据具体的需求和语言特点，选择合适的实现方式。