黑马程序员技术交流社区

标题: 关于折半查找 [打印本页]

---

作者: D_Time    时间: 2015-9-19 00:42
标题: 关于折半查找
//折半查找，返回要查找的数的位置
int searchItem(int arr[], int len, int key){
//先定义变量
    int low=0, high=len-1, mid;
//循环
    while (low<=high) {
    //计算mid的值
        mid = (low+high) / 2;//括号不能省略
    //判断key a［mid］
        if (key>arr[mid]) {
    //key>a[mid]    low = mid+1
            low = mid + 1;
        }else if (key<arr[mid]){
    //key<a[mid]    high = mid-1
            high = mid - 1;
        }else{
    //key==a[mid]   return mid
            return mid;
        }
  }
    return -1;
}


对于low和high和mid很模糊多感觉，怎么才能更好到理解呢？

---

作者: wjy0916    时间: 2015-9-19 08:10
百度百科：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

---

作者: bowenfei    时间: 2015-9-19 08:13
好好理解下就行了

---

作者: wjy0916    时间: 2015-9-19 08:23
刚才没写完，按回车就发了。。。。。。。。。。
假设是一个排好顺序的数列
0，1，2，3，4，5，6，7，8，9
int low=0, high=len-1, mid;  //high=9
mid = (low+high)/2   //mid=4
如果key>arr[mid]成立的话，就证明key再4的后边，所以要查找的序列就变成了 5.6.7.8.9
这个时候low=5，就从第5个开始了，到最后一个，
如果key<arr[mid]成立的话，就证明key在4的前边，这时查找的序列是0，1，2，3
这个时候high=3，从0--3了。
如果key=arr[mid]成立，那直接就找到了。
以此类推就是了。

---

作者: 苏子瞻201068    时间: 2015-9-19 09:57


#include<stdio.h>
int main() {  
        int t[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};  
        int a,b,c,mid;  a=0;b=14;  
       scanf("%d",&c);  
      while(a<=b)
     {   
          mid=(a+b)/2;  
          if(c==t[mid])  
          {    printf("%d",t[mid]);    break;   }               else if(c>t[mid])   
           {a=mid+1;   else b=mid-1;  }
           if(a>b)  
           printf("无此元素");  
           return 0;
      }
}

---

作者: 安若曦    时间: 2015-9-19 12:09
我主题里面有，可以看看

---

作者: D_Time    时间: 2015-9-19 22:48

安若曦 发表于 2015-9-19 12:09
我主题里面有，可以看看

嗯嗯，谢谢哈

---

作者: D_Time    时间: 2015-9-19 22:56

wjy0916 发表于 2015-9-19 08:23
刚才没写完，按回车就发了。。。。。。。。。。
假设是一个排好顺序的数列
0，1，2，3，4，5，6，7，8，9

多谢{:2_31:}

---

作者: D_Time    时间: 2015-9-19 22:57

bowenfei 发表于 2015-9-19 08:13
好好理解下就行了

求方法，求分享

---

作者: lixj1991    时间: 2015-9-19 23:09
每次在查找的时候，查找的数在min~mid，或者在mid~max的区间里，我们根据与mid的比较结果先确定查找数所在的区间，然后再相应地把这个区间的两个数取平均数缩小比较范围。

---

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

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