二分查找（Binary Search）

概述

二分查找是一种在有序数组中查找特定元素的高效算法。它的基本思想是将数组分成两部分，通过比较目标元素与中间元素的大小，不断缩小搜索区间，直到找到目标元素或者确定目标元素不存在。这种算法的时间复杂度为 $O(logn)$ ，相比于线性查找的 $O(n)$ 在处理大规模有序数据时效率更高。

二分查找的前提条件

数据必须是有序的。这是二分查找能够有效工作的关键。例如，对于一个整数数组，数组中的元素要么是升序排列（如 1, 3, 5, 7, 9），要么是降序排列。

二分查找的基本实现步骤（以升序数组为例）

步骤一：

初始化搜索区间 定义两个指针，left和right，分别指向数组的起始位置和结束位置。例如，对于数组int arr[] = {1, 3, 5, 7, 9};，如果要查找数组中的元素，初始时left = 0，right = sizeof(arr)/sizeof(arr[0]) - 1（这里sizeof(arr)/sizeof(arr[0])是计算数组的长度，减去 1 是因为数组下标从 0 开始）。

步骤二：

循环搜索 在left <= right的条件下进行循环。在每次循环中： 计算中间元素的下标mid = left+(right - left)/2。这样计算mid可以防止left和right很大时出现整数溢出的情况。 将目标元素target与中间元素arr[mid]进行比较。 如果target == arr[mid]，则表示找到了目标元素，返回mid。 如果target > arr[mid]，说明目标元素在中间元素的右侧，更新left = mid + 1，缩小搜索区间到中间元素的右侧部分。 如果target < arr[mid]，说明目标元素在中间元素的左侧，更新right = mid - 1，缩小搜索区间到中间元素的左侧部分。

步骤三：

目标元素不存在的情况 当left > right时，说明已经遍历完整个可能的搜索区间，目标元素不存在于数组中，此时可以返回一个表示未找到的标记，如 - 1。

代码示例

#include <iostream>
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = left+(right - left)/2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; 
}
int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    int result = binarySearch(arr, n, target);
    if (result == -1) {
        std::cout << "元素未找到" << std::endl;
    } else {
        std::cout << "元素在数组中的下标为: " << result << std::endl;
    }
    return 0;
}

二分查找的应用场景

如：在有序数组中查找元素，求解方程的根（数值分析），优化搜索问题 等，这里就不多多描述了