二分查找另类--[编程珠玑第四章]

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

如果最初的二分查找对你来说太简单了（大家肯定都是这么感觉的...）那么请你试一下其变型：在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 
  
   
#include 
   
     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<<"数字‘"<