某科学的二分查找

最近学了一点二分查找,虽然算法难度不是很大,但是在noip中还是比较重要的.

接下来是我对查找算法的思考.(若有疏漏之处,敬请指出)

1.查找方式有两种: 

　　（1）线性查找:什么意思呢？就是暴力的用for循环去扫整个数组，枚举就完事儿了。

　　（2）二分查找：利用中间节点mid进行标记，dio就完事儿了。

2.对于二分查找的一点引入：

　　猜数字的游戏全世界都玩过吧，给定一个范围，告诉大了还是小了，猜数字。

　　这是一个很简单也很经典的题目，也是二分的一个体现，这道题目的最佳策略很明显，折半思考就好了。

　　接下来举一个芒果（为什么是芒果？因为栗子不好吃）：

　　一个数n，在0-100之间：

　　这里假定n = 33

　　Q：50！

　　A:大了！

　　Q：25！

　　A：小了！

　　用了两次机会便将范围缩小到25-50，以此类推即可。

　　很快就能才出来，如果没明白或者想玩的，自己写一段rand试试看。

3.二分查找的懒汉写法：

　　（1）binary_search():

　　　　a.作用：查找数组中有没有n，有就返回true，没有就返回false。

　　　　b.使用方法：binary_search(数组名，数组名+数组长度，查找的数n)

　　（2）lower_bound():

　　　　a.作用:查找数组中第一个大于等于n的值

　　　　b,使用方法:lower_bound(数组名, 数组名 + 数组长度,  查找的数n)

　　（3）upper_bound();

　　　　a.作用:查找数组中第一个大于n的值

　　　　b,使用方法:upper_bound(数组名, 数组名 + 数组长度,  查找的数n)

4.具体的使用环境：

　　一个升序的数组中可以使用。

5.使用的题目芒果（都说了栗子不好吃）

　　1）两数相加为一个确定值：

　　　　题目描述：

　　　　给你一个长为n的数组，一个数m，看看数组中有没有两个数字和是m, 如果存在，输出这两个数；如果不存在，输出“NO”：

　　　　样例输入：

　　　    4

　　　　2 5 1 3

　　　　6

　　　　样例输出;

　　　　1 5

这里主要用的是binary_search（）这个函数，难点思路在于，我们可以将在数组里面找到一个数字是否为m - num[i];
简单来讲就是求出当前这个数字与给定的和M的差值，如果后面的数组num[i]中有这个数，则这道题目已经完成了（所以还是很简单的）

题目的解析

#include<bits/stdc++.h>//万能库，挺好用的
using namespace std;

int num[100005];
    int n, m;
    bool f = false;//判断是否找到数字的判断条件，初始值为没有找到设为false

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> num[i];
    cin >> m;
    sort(num,num+n);
    for (int i = 0; i < n; i++) {
        if (binary_search(num + i + 1,num + n,m-num[i])) { //就是我们刚刚说的解析中球的差值
            f = true;//找到了以后就这样了
            cout << num[i] << " " << m - num[i] << endl；
            break;
        }
    }
    if (!f) {
        cout << "No" << endl;//判断没有的情况
    }
    return 0;
}
        

代码实现

　　2）求出数组中最接近N的数字：

　　　　给你一个数组num,一个问题N，在数组中找到最接近这个数字的数字并输出。

　　　　样例输入：

　　　　3

              1 2 3

　　　　4

　　　　样例输出：

　　　　3

这题有两种思路可以实现。
首先就是用lower_bound的实现方法：
1.我们知道，lower_bound() 返回的是第一个大于等于n的数字，所以我们需要一个在n左边且最靠近n的数字，简单来讲就是，找到最大的那个小于n的数字，实现起来非常简单，就是用lower_bound()求出来的p1往前一位，就是P1-1 这个就是我们要求的左端数字。
2.接下来是最简单的一步，就是比较左右两个数字对给定数字n的距离即可。

接下来是upper_bound()的实现方法：
1.由之前lower_bound()的实现方法，我们可以知道，upper_bound()只需要做出如上操作即可，求出一个p 用哪个p - 1 就是我们所需要的两个数值。
2.比较即可

View Code

　　代码就不写出来了，自己练练手感哈。（注意p1,p2的特判，一个判定是否为n，另一个判定，是否为-1）

　　那么二分查找就讲到这里，自己找题目去练吧！