C++二分查找

C++二分查找：

二分查找属于分治算法，相对于遍历查找要简便快捷许多，其思路是：定义左指针l和右指针r，取其中值mid，接下来，判断要找的数f，看他如果比a[mid]小，那r=mid-1，表示在左半区间,否则判断a[mid]<x,那l=mid+1,表示在右半区间，在否则的话，那就是找到了，found=mid，然后break跳出循环，否则继续执行。

while(n--)
    {
    int l,r,mid,found=0;//found表示找到了，mid表示中值，l左边，r右边。
       l=1;
       r=m;
       while(l<=r)
       {
            mid=(l+r)/2;
            if(a[mid]>x)//左半区间
            {
                r=mid-1;
        }
        else if(a[mid]<x)//右半区间
        {
            l=mid+1;
        }
        else
        {
            found=mid;
            break;
        }
       }
        if(found==mid)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }

练习题目（本人自己出的）：

水族馆 (aquarium.cpp)

【题目描述】 你热爱鱼类，因此决定建造一个水族馆。你有一个由 n 列构成的珊瑚，其中第 i 列的高度是 ai单位。 之后，你将按照以下方式围绕珊瑚建造一个水槽： 1. 选择一个整数 h≥1 — 水槽的高度。在水槽的两侧建造高度为 h 的墙壁。 2. 然后，将水注入水槽中，使每列的高度都是 h，除非珊瑚比 h 更高；如果是这样，那么该列就不 应添加水。 例如，对于 a=[3,1,2,4,6,2,5] 和高度 h=4，你将最终需要使用总共 w=8 单位的水，因为（4-3）+（4-1）+（4-2）+（4-2）=8，因为6与5比4大，所以不能减。 你最多可以使用 x 单位的水来填满水槽，但你想要建造可能的最大水槽。你可以选择的最大 h 值是 多少？ 【输入格式】 第一行包含一个整数 t (1≤t≤104 ) — 测试用例的数量。 每个测试用例的第一行包含两个正整数 n 和 x (1≤n≤2×105 ; 1≤x≤109 ) — 珊瑚的列数和最大可 以使用的水量。 每个测试用例的第二行包含 n 个以空格分隔的整数 ai (1≤ai≤109 ) — 珊瑚的高度。 所有测试用例中 n 的总和不超过 2×105。 【输出格式】 对于每个测试用例，输出一个正整数 h (h≥1) — 水槽可以达到的最大高度，以便你最多需要使用 x 单位的水来填满水槽。 我们有证据证明，在这些约束条件下，这样的 h 值总是存在的。

【输入样例】

5

7 9

3 1 2 4 6 2 5

3 10

1 1 1

4 1

1 4 3 4

6 1984

2 6 5 9 1 8

1 1000000000

1

【输出样例】

4

4

2

335

1000000001

【样例说明】 第一个测试用例如题目中所示。当 h=4 时，我们需要 8 单位的水，但如果将 h 增加到 5，我们需要 13 单位的水，这超过了 x=9。因此，h=4 是最优的选择。 在第二个测试用例中，我们可以选择 h=4，然后向每一列添加 3 单位的水，总共使用 9 单位的水。可以 证明这是最优的选择。