二分查找另类--【编程珠玑第四章】

这是《编程珠玑》第四章的问题：

如果最初的二分查找对你来说太简单了（大家肯定都是这么感觉的...）那么请你试一下其变型：在p中返回t在数组x中第一次出现时的位置（即如果一个数组多次出现的话，原先的算法所返回的是众多位置的中的任意一个）。你的代码应该对数组元素进行对数次比较，可能要进行log₂N此这样的比较才能完成此二分查找。

这题的关键是找到最先开始出现的位置，如对数组：{0, 5, 5, 5, 5, 14, 16, 16, 50, 65, 70};

若用之前的二分查找算法：

可是我们明显可以发现5是在数组中的第二个位置的（当然此时数组下标是1）；

最开始算法经过二分查找，首先mid = (low + high) = 5;查到了14，发现x < a[mid]; high = mid - 1 = 4;

mid = 2;这时查到了5，最后输出5在数组中第三位（mid + 1）（数组由下标0开始，各位别混了...）

可是现在我们需要查找的是最先出现的，即在之前：

if(s[mid] == x)
           return mid;

这个时候并不能返回mid，因为我们无法确认是否是第一个出现；

这时则应该继续进行二分查找，直到找不到符合条件为止：

即：

    int mid;
    int index = -1;

    while(low <= high)
    {
        mid = (low + high) / 2;  //二分查找

        if(s[mid] == x)  //查找到目标数据
        {
            index = mid;  //记录下标
            high = mid - 1;  //继续向前匹配，是否能继续找到
        }

        else if(s[mid] < x)
           low = mid + 1;
        else high = mid - 1;
    }

    return index;

建立一个标记的下标index，初始为-1，查到到目标数据，则对index进行修改；

最后返回index最后一次的值，这个值就是最先出现的值：

#include <iostream>
#include <cstring>

using namespace std;

int BinarySearch(int* s, int x, int low, int high)
{
    int mid;
    int index = -1;

    while(low <= high)
    {
        mid = (low + high) / 2;  //二分查找

        if(s[mid] == x)  //查找到目标数据
        {
            index = mid;  //记录下标
            high = mid - 1;  //继续向前匹配，是否能继续找到
        }

        else if(s[mid] < x)
           low = mid + 1;
        else high = mid - 1;
    }

    return index;
}

int main()
{
    int s[] = {0, 5, 5, 5, 5, 14, 16, 34, 50, 65, 70}; //递增序列，也可运用动态数组存数据

    cout<<"请输入需要查找的数：";
    int num;
    cin>>num;

    int n = sizeof(s) / sizeof(int);

    int index = BinarySearch(s, num, 0, n - 1);
    if(index >= 0)  //根据返回值判断是否在数组中
        cout<<"数字‘"<<num<<"’ 在数组第"<<index + 1<<"位最先出现, "<<"即下标是："<<index<<endl;
    else
        cout<<"数字"<<num<<"不在数组中"<<endl;
    return 0;
}

当然若是想知道查找目标是否多次出现，也可在if(s[mid] == x)里面添加自己的标识，自行输出即可，有兴趣的可以试试...

测试数据较少，若有错误，请大家不吝赐教。

欢迎大家指点...o(∩_∩)o