黑马程序员技术交流社区

标题: 大家一起来交流：用折半查找法查找数组中存在的数 [打印本页]

---

作者: JamesLucky    时间: 2015-6-22 23:35
标题: 大家一起来交流：用折半查找法查找数组中存在的数
在查找数组中的数时，用折半法查找比从头至尾搜索式查找更有效率。
算法分析：
1.low=1, high=len,  设置要查找的区间；
2.low>high时，查找失败；
3.low<=high时，mid=(low+high)/2, 折半查找，找中点
  1)key<arr[mid], high=mid-1, 在中点左半区选取区间
  2)key>arr[mid], low=mid+1, 在中点右半区选取区间
  3)key=arr[mid],查找成功，返回并打印数据元素表中位置

程序实现：
#include<stdio.h>       
int search(int arr[],int len,int key){
int low = 0, high = len-1, mid;
while (low<=high){
          mid = (low+high)/2;
          if(key>arr[mid]){
                   low = mid+1;
              }else if(key<arr[mid]){
                        high = mid-1;
              }else{
                      return mid;
              }
   }
   printf("数组不存在你要查找的数");
   return -1;
}

int main(){
        int a[] = {2,4,7,10,15,19,23,27,32,35,38,41,45,49,50};
        int key;
        printf("请输入要查找的数");
        scanf("%d",&key);
        int loc = search(a, 15, key);
        printf("loc = %d\n", loc);
       
        return 0;
}
编译后运行结果：输入3时，显示数组不存在要查找的数loc=-1
输入32时，显示loc=8

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2