二分

〇、返回

一、引出

想象一下，一个工人需要在一条长水管中找到一个漏水点。为了高效地找到漏水点，工人决定每次检查中间的部分。如果有水，那么漏水点就在右边；如果没水，那么漏水点就在左边（假设水从管子左边流入，右边流出）。这样每次都可以将搜索范围缩小一半，直到找到确切的漏水点。这种逐步缩小搜索范围的方法，就是二分算法的基本思想。

二、概述

二分算法（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的核心思想是通过每次将搜索区间减半来快速定位目标值的位置。相比于线性搜索，二分搜索在大数据量的情况下具有显著的时间效率优势。

三、算法步骤

1. 初始化

设定搜索区间的初始边界，通常为数组的起始位置 left=0 和结束位置 right=n-1（其中 n 是数组的长度）。

2. 中间位置

计算当前搜索区间的中间位置 mid，使用公式 mid=(left+right)/2，如果数据大可以用 mid=left+(right-left)/2，避免溢出。

3. 比较与缩小范围

如果中间位置的值 arr[mid] 等于目标值 target，则找到目标值，返回 mid。

如果 arr[mid] 小于 target，则目标值在右半区间 [mid+1,right] 中，因此更新 left=mid+1。

如果 arr[mid] 大于 target，则目标值在左半区间 [left,mid-1] 中，因此更新 right=mid-1。

4. 终止条件

当 left 超过 right 时（即 left>right），表示搜索区间为空，目标值不存在于数组中，返回 -1 或其他表示未找到的值。

四、适用情况

二分算法适用于以下情况

有序数组：数组必须是有序的（升序或降序）。

查找特定值：需要在数组中查找一个特定的值。

优化搜索：在大数据量的情况下，相比线性搜索，二分搜索能显著提高效率。

五、代码示例（C++）

以下是二分算法的基本实现

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n;

    cin>>n;

    vector<int> a(n);

    for (int i=0;i<n;i++) {

        cin>>a[i];

    }

    int left=0,right=n-1,ans=-1;

    while (left<=right) {

        int mid=left+(right-left)/2;

        if (a[mid]==target) {

            return mid;

        } else if (a[mid]<target) {

            left=mid+1;

        } else {

            right=mid-1;

        }

    }

    cout<<ans<<"\n";

    return 0;

}

六、时间复杂度

二分算法的时间复杂度为 O(log n)，其中 n 是数组的长度。每次迭代都将搜索区间减半，因此能够在对数时间内完成搜索。

七、总结

二分算法是一种高效且简洁的搜索算法，特别适用于有序数组中的查找问题。其核心思想是通过每次将搜索区间减半来快速定位目标值的位置，时间复杂度为 O(log n)，在大数据量的情况下具有显著的优势。理解并掌握二分算法，不仅可以解决基本的查找问题，还可以应用于更多复杂的场景，如查找第一个等于给定值的元素、查找最后一个小于等于给定值的元素等。总之，二分算法是每个程序员都应该熟练掌握的基本技能之一。