二分搜索

苏丙榅2024-06-282024-07-04

1. 二分搜索概述

二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索是一种高效的查找算法，适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割，从而快速缩小查找范围。

二分搜索每次把搜索区域减少一半，时间复杂度为 O(log_n)（n代表集合中元素的个数）。

二分搜索的基本步骤如下：

初始条件：将搜索范围设为数组的整个区间。
查找中间元素：计算当前区间的中间索引。
比较中间元素：将中间元素与目标值进行比较：
- 如果中间元素等于目标值，查找成功，返回中间索引。
- 如果中间元素小于目标值，将搜索范围缩小到右半部分。
- 如果中间元素大于目标值，将搜索范围缩小到左半部分。
重复步骤 2 和 3，直到找到目标值或搜索范围为空。

在下图中为大家展示了二分搜索的过程：

2. 递归实现

递归实现二分搜索的代码如下：

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

int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) 
{
    if (left <= right) 
    {
        int mid = left + (right - left) / 2; 
        if (arr[mid] == target) 
        {
            return mid;
        }
        if (arr[mid] > target) 
        {
            return binarySearchRecursive(arr, left, mid - 1, target);
        }
        return binarySearchRecursive(arr, mid + 1, right, target);
    }
    return -1;
}

int main() 
{
    vector<int> arr = { 2, 3, 4, 10, 40 };
    int target = 10;
    int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);

    if (result != -1) 
    {
        cout << "元素在索引 " << result << " 处找到" << endl;
    }
    else 
    {
        cout << "元素未找到" << endl;
    }

    return 0;
}

代码解释

函数定义：binarySearchRecursive 函数接收一个数组 arr、搜索范围的左右边界 left 和 right，以及目标值 target。
终止条件：当 left 大于 right 时，搜索范围为空，返回 -1 表示未找到目标值。
计算中间索引：使用 left + (right - left) / 2 计算中间索引，避免溢出。
比较中间元素：检查中间元素是否等于目标值，如果等于则返回中间索引。
递归调用：根据中间元素与目标值的大小关系，递归调用函数搜索左半部分或右半部分。

3. 非递归实现

非递归实现二分搜索的代码如下：

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

int binarySearchIterative(const vector<int>& arr, int target)
{
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
        {
            return mid;
        }

        else if (arr[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

int main()
{
    vector<int> arr = { 2, 3, 4, 10, 40 };
    int target = 10;
    int result = binarySearchIterative(arr, target);

    if (result != -1)
    {
        cout << "元素在索引 " << result << " 处找到" << endl;
    }
    else
    {
        cout << "元素未找到" << endl;
    }

    return 0;
}