寻找脚码----2013年2月24日

     题目来自:《C语言精选名题百则技巧篇》

     问题描述:已知一个整数数组x[],其中的元素彼此都不相同，而且也已经从小到大排列好。请用比较大小，相等的方式编写一个程序，找出给定的数组中是否有一个元素满足x[i]==i(注意:在代码中是从0开始索引的，也就是x[0]是第一个数，所以对应于代码也就是x[i]==i+1)的关系。举例而言，如果x[]={-2,-1,3,7,8},x[3]=3,因此3就是答案。

     思路:利用x[]中的元素彼此都不相同而且从小到大排列，可以用二分查找法。代码很简单。

#include <stdio.h>
 #define MAX 1000

 //prototypes
 int BinarySearch(int a[],int high,int low);

 int main()
 {
     int x[MAX]={-2,2,4,7,8};//x[i]=i+1;
     int low=0;
     int high=4;
     int result=BinarySearch(x,high,low);
     printf("%dn",x[result]);
 }

 int BinarySearch(int a[],int high,int low)
 {
     while(low<=high)
     {
         int mid=low+(high-low)/2;
         if(a[mid]==mid+1)
             return mid;
         else if(a[mid]>mid+1)
             high=mid-1;
         else
             low=mid+1;
     }
     return -1;
 }

     如果你觉得我的文章对你有帮助，请赞一下，非常感谢!