查找---二分查找-EW帮帮网

一、算法核心概念

二分查找（Binary Search）又称折半查找，是一种针对有序数组的高效查找算法。其核心思想是通过不断将查找范围减半，快速缩小目标元素的可能位置，最终实现O(log n)的时间复杂度。与线性查找（逐个遍历，O(n)复杂度）相比，二分查找在数据量较大时效率提升极其显著。

二、适用条件

二分查找的应用有严格前提：

数组必须有序（升序或降序，本文以升序为例）；
支持随机访问（如数组结构，可通过索引直接访问元素，链表不适用）；
数据静态或修改频率低（若需频繁插入/删除，维护有序性成本高）。

三、算法原理

假设存在升序数组arr，目标值为target，查找步骤如下：

定义查找区间的左右边界：low = 0（起始索引），high = n-1（末尾索引，n为数组长度）；
计算区间中点：mid = low + (high - low) / 2（避免low + high溢出）；
比较arr[mid]与target：
- 若arr[mid] == target：找到目标，返回mid；
- 若arr[mid] > target：目标在左半区间，更新high = mid - 1；
- 若arr[mid] < target：目标在右半区间，更新low = mid + 1；
重复步骤2-3，直到low > high（区间为空，目标不存在），返回-1。

四、时间与空间复杂度

时间复杂度：每次查找范围减半，最多需要log₂n次操作，故为O(log n)。例如，n=10⁶时，最多仅需20次查找（2²⁰≈10⁶）。
空间复杂度：
- 非递归实现：仅使用常数额外空间，O(1)；
- 递归实现：递归调用栈深度为log₂n，O(log n)。

五、C/C++实现示例

1. 基础版（非递归）

功能：在升序数组中查找目标值，返回索引（不存在则返回-1）。

#include <iostream>
#include <vector>
using namespace std;

// 非递归实现二分查找
int binarySearch(const vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    
    while (low <= high) {
        // 计算中点（避免low + high溢出）
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            return mid; // 找到目标，返回索引
        } else if (arr[mid] > target) {
            high = mid - 1; // 目标在左半区间
        } else {
            low = mid + 1; // 目标在右半区间
        }
    }
    return -1; // 目标不存在
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;
    int index = binarySearch(arr, target);
    
    if (index != -1) {
        cout << "目标 " << target << " 位于索引 " << index << endl;
    } else {
        cout << "目标 " << target << " 不存在" << endl;
    }
    return 0;
}

关键细节：

中点计算用low + (high - low)/2而非(low + high)/2，避免low + high超过int最大值导致溢出；
循环条件为low <= high（当low == high时，区间仍有一个元素需检查）；
边界更新用mid ± 1（排除已检查的mid位置，避免死循环）。

2. 递归版

功能与基础版一致，通过函数递归实现查找。

#include <iostream>
#include <vector>
using namespace std;

// 递归实现二分查找
int binarySearchRecursive(const vector<int>& arr, int target, int low, int high) {
    // 递归终止条件：区间为空
    if (low > high) {
        return -1;
    }
    
    int mid = low + (high - low) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        // 递归查找左半区间
        return binarySearchRecursive(arr, target, low, mid - 1);
    } else {
        // 递归查找右半区间
        return binarySearchRecursive(arr, target, mid + 1, high);
    }
}

int main() {
    vector<int> arr = {2, 4, 6, 8, 10};
    int target = 6;
    int index = binarySearchRecursive(arr, target, 0, arr.size() - 1);
    
    if (index != -1) {
        cout << "目标 " << target << " 位于索引 " << index << endl;
    } else {
        cout << "目标 " << target << " 不存在" << endl;
    }
    return 0;
}

特点：代码简洁但递归调用有额外栈空间开销，数据量极大时可能栈溢出，实际中更推荐非递归版本。

3. 变种：查找重复元素的第一个/最后一个位置

当数组存在重复元素时（如[1, 2, 2, 2, 3]），基础版可能返回任意一个匹配位置。若需查找第一个或最后一个目标元素，需调整边界更新逻辑。

示例：查找第一个等于target的元素

#include <iostream>
#include <vector>
using namespace std;

// 查找第一个等于target的元素索引
int findFirstOccurrence(const vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int result = -1; // 记录结果
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            result = mid; // 暂存当前位置
            high = mid - 1; // 继续向左查找更早的位置
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

// 查找最后一个等于target的元素索引
int findLastOccurrence(const vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int result = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == target) {
            result = mid; // 暂存当前位置
            low = mid + 1; // 继续向右查找更晚的位置
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return result;
}

int main() {
    vector<int> arr = {1, 2, 2, 2, 3, 4};
    int target = 2;
    
    int first = findFirstOccurrence(arr, target);
    int last = findLastOccurrence(arr, target);
    
    cout << "第一个 " << target << " 位于索引 " << first << endl; // 输出1
    cout << "最后一个 " << target << " 位于索引 " << last << endl; // 输出3
    return 0;
}

逻辑调整：

找到匹配元素时不立即返回，而是继续向目标方向（左/右）收缩区间，直到区间为空，最终记录的位置即为第一个/最后一个匹配项。

六、常见错误与边界处理

死循环：若边界更新时未排除mid（如high = mid而非high = mid - 1），可能导致low与high无法收敛（例如low=high=mid时，循环永不结束）。
溢出问题：中点计算若用(low + high)/2，当low和high均接近int最大值时，low + high会溢出为负数，导致mid计算错误。
空数组处理：需提前判断数组长度为0的情况，直接返回-1。
目标值超出数组范围：若target < arr[0]或target > arr[n-1]，应快速返回-1，减少无效循环。

七、应用场景

字典查询：如通讯录按姓名首字母排序后查找联系人；
数值逼近：如求一个数的平方根（整数部分）、寻找函数零点；
数据库索引：数据库中B+树索引的查找逻辑基于二分思想；
日志分析：在有序日志（如按时间排序）中定位特定时间点的记录。

二分查找是一种“以空间换时间”的经典算法，其高效性依赖于有序数据和随机访问特性。实际应用中需注意边界处理和重复元素场景，根据需求选择基础版或变种实现。

查找---二分查找