当前位置：首页 > article >正文

【算法篇·更新中】C++秒入门(附练习用题目)

article 2025/1/31 1:29:47

一.二分

1.二分查找

我们来看这样一道题：

有一个保证有序的数组a，它的长度为n。现在我们需要知道这个序列是否含有x。
数据范围：保证n<=1e9

我们看到这道题之后，第一时间想到的就是暴力枚举了，可是我们发现直接枚举会超时。所以我们只能使用一种n logn时间复杂度的算法。
那么能满足n logn时间复杂度的算法，二分查找是首选项。

二分查找怎么找？

二分查找，俗称折半查找法。
折半查找法，顾名思义，每次将查找范围缩小，来达到优化时间的目的。
我们可以设序列a={1，10，25，30，101，234}，l为查找的左边界（搜索起点），r为查找的右边界（搜索终点），要查找它是否包含的数是4。
那么搜索起点就是1，终点就是n（a的长度）。
我们一定会用循环，可是，用哪种循环？条件是什么？
很明显，有条件才循环，所以用while循环
由于左边界在往右搜，右边界在往左搜，所以条件是l<r
原理：
左边最大的都小于了这个数，故不可能这个数在左边存在，同样，右边最小的都大于了这个数，故不可能这个数在右边存在。
如果最后搜索完了却依然没有找到，就输出No；
核心代码（模板）：

l=1,r=n;
while(l<=r)
{
    mid=(l+r)/2;
    if(a[mid]>m[i])
    {
        r=mid-1;
    }
    else if(a[mid]<m[i])
    {
        l=mid+1;
    }
    else
    {
        cout<<"Yes"<<endl;
        return 0;
    }
}
if(l>r)
{
    cout<<"NO"<<endl;
}