传火者 - 二分查找理论基础

今天 我们来讲个非常实用的数据查找算法——二分查找

0.算法是什么

算法就是机器执行一件事的解题过程，例如我们要泡泡面，那么就有一下几个步骤：

1. 烧水
2. 放面饼
3. 加调料

这里泡泡面的步骤被在计算机科学中称为算法

计算机科学中还有很多实用的算法，例如寻路用的 A-star 算法，排序数据用的快速排序算法。

1.二分查找是什么

二分查找是一个高效的搜索算法，核心思想就是分而治之，二分查找的使用要求就是被查找的这组数据必须有序

2.如何理解二分查找

我们可以举一个简单的例子来理解二分查找：猜数字游戏

游戏要求我们找到一个范围为 1-100 的随机数，我们可以把玩这个游戏近似地看成查找算法。

线性查找算法，会从 1 逐个询问，最坏情况时间复杂度为

而二分查找，因为 1-100 这个范围可以视为一组有序的数据，我们先查找最中间的数据 50,如果大了，就去到 51-100 的范围内再进行一遍这个过程，依次类推，你总会找到需要查找的目标。平均时间复杂度

3.应用场景

• 查字典：纸质字典二分定位
• 游戏开发：在排序好的坐标列表内检测碰撞

💡 重要提示：若数据无序，需要先排序再使用二分查找。排序可能会抵消二分查找的效率优势，例如快速排序+二分查找

4.实现二分查找

以下是二分查找的一个 C/C++实现:

int binarySearch(int arr[],int size,int target){
    int left=0;
    int right=size-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;
}

5.实战

洛谷P2249

如果用线性搜索法，你至多需要查找次,也就是次，显然会TLE,但由于输入的数据单调不减（就是升序排序），可以使用二分查找来压缩时间复杂度