7-1 二分法查找

有一个有序整型数组array，元素为1,2,5,6,7,12,15,67,88,99,100,200。输入一个元素a,利用二分查找法查找a元素所在的位置。

二分法查找适用于数据量较大时，但是数据需要先排好顺序。
主要思想是：（设查找的数组区间为array[low,high]）
算法开始可设置low=0;high=n-1（n为一维数组元素的个数）
（1）确定该区间的中间位置mid
（2）将查找的值a与array[mid]比较。若相等，mid为查找位置；若low>high时，算法结束。
否则确定新的查找区域，继续二分查找。
区域确定如下：array[mid]>a 由数组的有序性可知,a可能在新的区间为array[low,……，mid-1]
array[mid]<a 查找区间为array[mid+1,……，high]。

输入格式:

输入要查找的元素a

输出格式:

如果找到，输出found!、找到的位置和查找的次数，如果没有找到，输出not found!。

输入样例:

在这里给出一组输入。例如：

12

输出样例:

在这里给出相应的输出。例如：

found! 5 1

输入样例:

在这里给出一组输入。例如：

13

输出样例:

在这里给出相应的输出。例如：

not found!

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include<stdio.h>
#include<stdlib.h>
int main(){
    int d[]={1,2,5,6,7,12,15,67,88,99,100,200};
    int low=0,hight=11;
    int x;
    scanf("%d",&x);
     int count=0;int found=1;
    while(low<=hight){
        int mid=(low+hight)/2;
        if(d[mid]==x){
            count++;
            printf("found! %d %d",mid,count);
            found=0;
            break;
        }
        else if(d[mid]<x){
            low=mid+1;
            count++;
        }
        else {
            hight=mid-1;
            count++;
        }
    }
    if(found)
    printf("not found!");
    return 0;
}