二分搜索（递归）与（非递归）

题目描述
使用递归算法，实现二分搜索。
输入
多组数据输入，每组第一个数字为数组的长度n，然后输入n个整数，最后输入待查询的值。
输出
输出待查询值所在的位置，如果没有找到，则返回-1。
样例输入
3 1 2 3 2
4 0 1 3 4 2
样例输出
2
-1

思路：其实递归与非递归的思路基本一致，都是先中间再两边，找到了就返回元素下标，没找到就继续缩小区间，直到找到为止，详细思路我会注释在代码里面，如有不对，欢迎各位大佬指出。


递归代码

#include <bits/stdc++.h>
using namespace std;
int a[100000];
int digui(int k, int left, int right)
{
   
    int mid = left + ((right - left) >> 1);
    // int mid = (left + right) / 2;
    //mid=(left+right)/2 等价于 left+(right-left)/2,这样写能防止right+left溢出，写为位运算
    //mid=left+（（right-left）>>1）的形式更高效，由于位运算的优先级低于逻辑运算，所以要在多项式中的位运算上加上小括号，不然程序就会错误
    //注意：left一定要写在前面，写在后面的话右移的位数就是（left+1）
    if (left <= right)
    {
                       //以下内容读者可以手动模拟一遍
        if (a[mid] == k) //如果找到了就返回数组下标对应值
            return mid;
        if (a[mid] > k) //如果所要找的k值在右边，就继续递归右边区间（区间缩小一半）
            return digui(k, left, mid - 1);
        else //否则就递归左边区间
            return digui(k, mid + 1, right);
    }
    return -1; //如果没找到就返回题目要求的-1
}
int main()
{
   
    int n, k;
    while (cin >> n)
    {
   
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        cin >> k;
        //这里一定要注意，这是要找K值，所以k一定要作为参数放入函数，否则函数就不能正常运行
        cout << digui(k, 1, n) << endl;
    }
    return 0;
}

非递归代码

#include <bits/stdc++.h>
using namespace std;
int a[100000];
int digui(int k, int n)
{
   
    int left = 1, right = n;//分别让left与right等于数组左右两边界
    while (left <= right)
    {
   
        int mid = (right + left) / 2;//建议使用上述的位运算，位运算能够大大提高程序的效率
        if (a[mid] == k)
            return mid;
        else if (k > a[mid])
            left = mid + 1;//区间减半，下同
        else
            right = mid - 1;
    }
    return -1;
}
int main()
{
   
    int n, k;
    while (cin >> n)
    {
   
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        cin >> k;
        cout << digui(k, n) << endl;
    }
    return 0;
}

二分搜索升级版

题目描述
设a[0:n-1]是已排好序的数组。请改写二分搜索算法，使得当待搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素的位置j；当待搜索元素x在数组中时，返回的i和j相同，均为x在数组中的位置
输入
多组数据输入，每组第一个数字为数组的长度n，然后输入n个整数，最后输入带查询的值x。
输出
输出小于x的最大元素的位置i和大于x的最小元素的位置j；当待搜索元素x在数组中时，返回的i和j相同，均为x在数组中的位置
样例输入
3 1 2 3 2
4 0 1 3 4 2
样例输出
2 2
2 3

这个题目稍微比上面的难一点，不过实现的过程依然是上述的思想

#include <bits/stdc++.h>
using namespace std;
int a[100000];
int pos1, pos2, n, x;
void search(int l, int r, int x)
{
   
    if (l > r) //递归结束条件之一
    {
             //如果此时左边大于右边，那么大于k值得是左边所对应的元素值，当然小于K值得就是右边对应的元素值
        pos1 = r, pos2 = l;
        return;
    }
    int mid = (l + r) / 2; //建议使用位运算
    if (a[mid] == x)       //递归结束条件之二
    {
   
        pos1 = pos2 = mid;
        return;
    }
    else if (a[mid] > x)
        search(l, mid - 1, x); //递归左边
    else
        search(mid + 1, r, x); //递归右边
}
int main()
{
   
    while (cin >> n)
    {
   
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        cin >> x;
        int l = 1, r = n; //让他们分别为数组左右两端点的下标值
        search(1, n, x);  //调用函数
        cout << pos1 << ' ' << pos2 << endl;
    }
    return 0;
}