首页 > 代码库 > 折半查找
折半查找
所谓折半查找，又称二分查找，是一种在有序数组中查找某一特定元素的搜索算法。优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
复杂度：
时间复杂度：由于折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)，其时间复杂度使得在数据量很大的时候，使用折半查找显得异常高效（就像"汉诺塔"和"数麦粒"的故事一样，增速迅猛，麦粒总数和金片移动次数均为2^64-1一样，那时人们面对海量数据毫无概念，根本想象不到数据有多大），直观点假设有40亿个有序序列，我们要查找其中的一个时最多需要32次比较，其高效性在这里就体现的淋漓尽致了。
空间复杂度：O(1)。
要求：
数据必须采用顺序存储结构，必须按关键字大小有序排列。
下面举一例子:
问题描述:
有一个数组A[10], 里面存放了10个整数，顺序递增。
A[10] = {2, 3, 5, 7, 8, 10, 12, 15, 19, 21}
任意输入一个数字n，用折半查找法找到n位于数组中的位置。如果n不属于数组A，显示错误提示。
【分析】
这是一个折半查找法的简单应用。折半查找不仅可以通过查找关键字对文件记录进行查找，也可应用于简单的数组，顺序表结构等查找。在这里同样要求数组中的元素有序。
程序清单
# include <stdio.h>bin_search(int A[], int n, int key){ int low, high, mid; low = 0; high = n-1; while(low <= high) { mid = (low + high) / 2; if(A[mid] == key) return mid; //查找成功，返回mid if(A[mid] < key) low = mid + 1; //在后半序列中查找 if(A[mid] > key) high = mid - 1; //在前半序列中查找 } return -1; //查找失败，返回-1}int main(void){ int A[10] = {2, 3, 5, 7, 8, 10, 12, 15, 19, 21}; int i, n, addr; printf("The contents of the Array A[10] are\n"); for(i=0; i<10; i++) printf("%d ", A[i]); //显示数组A中的内容 scanf("%d", &n); //输入待查找的元素 addr = bin_search(A, 10, n);//折半查找，返回该元素在数组中的下标 if(-1 != addr) printf("%d is at the %dth unit is array A\n", n, addr); else printf("There is no %d in array A\n", n);//查找失败 return 0;}在C-Free 5.0中的输出结果是:
The contents of the Array A[10] are
2 3 5 7 8 10 12 15 19 21
10
10 is at the 5th unit is array A
Press any key to continue . . .
我的实现方式如下: （贴出自己的实现方式只是为了保存当时的思路，用于反思自己和做一些总结，因为我觉得没有自己的思路，一味记忆书上的代码片段，效果不大，记忆不深刻，且效率不高。所以我是在了解了基本的编码思想，做出正确答案后（至少表面上测试正确），又看的书上给出的答案。）
# include "stdio.h"int binarysearch(int a[], int length, int key){ int low = 0; int high = length-1; int mid = (low + high) / 2; while(high >= low) //循环终结条件 { if(a[mid] == key) return mid; if(key > a[mid]) //与程序清单不同，这里使用if-else来减少循环比较的次数。 { low = mid + 1; mid = (low + high) / 2; continue; //与程序清单不同，因为mid的值可能在这里被改变，因此需要continue } else(key < a[mid]) { high = mid - 1; mid = (low + high)/ 2; continue; } } return -1;}int main(void){ int a[10] = {2, 3, 5, 7, 8, 10, 12, 15, 19, 21}; int n; scanf("%d", &n); int value = http://www.mamicode.com/binarysearch(a, 10, n);"ERROR, the element what you want to search is not found!\n"); else printf("the index of the element is %d\n", value); return 0;}在C-Free 5.0中的输出结果是:
12
the index of the element is 6
Press any key to continue . . .
推荐使用方式：（取自：程序员编程艺术一书）
//二分查找V0.1 实现版//copyright@2011 July//随时欢迎读者找bug，email：zhoulei0907@yahoo.cn。//首先要把握下面几个要点：//right=n-1 => while(left <= right) => right=middle-1;//right=n => while(left < right) => right=middle;//middle 的计算不能写在while 循环外，否则无法得到更新。int binary_search(int array[],int n,int value){ int left=0; int right=n-1; //如果这里是int right = n 的话，那么下面有两处地方需要修改，以保证一一对应： //1、下面循环的条件则是while(left < right) //2、循环内当array[middle]>value 的时候，right = mid while (left<=right) //循环条件，适时而变 { int middle=left + ((right-left)>>1); //防止溢出，移位也更高效。同时，每次循环都需要更新。 if (array[middle]>value) { right =middle-1; //right 赋值，适时而变 } else if(array[middle]<value) { left=middle+1; } else return middle; //可能会有读者认为刚开始时就要判断相等，但毕竟数组中不相等的情况更多，如果每次循环都判断一下是否相等，将耗费时间 } return -1;}一点补充：
1.这里对为什么用middle=left + ((right-left)>>1)(注意：加法的优先级大于移位)而不是middle=(right+left) >>1做一个说明，引用我先前的一条评论，用后者:"mid可能越界，比如说，初始状态下low取值0，high取值2^31-1，那么第一次求值mid为2^30-1，假设所要查找的值value在中值mid右侧，这时候求和（2^31-1）+（2^30-1）为负值，再除以2依然为负，这时候a[mid]就出现越界了，如此看来，出现越界的情况蛮多的，比如任意两个大于2^30的low和high求和都会得负数"。因此最好用mid = low + ((high-low) >> 1) 就不会出现上述情况了。
2.比较次数：假设有n个元素，采用折半查找是，最多需要比较的次数是：(log n + 1)向下取整，比方说n取8，则最多比较4次，n取9，最多比较次数依然为4次，依次类推。
折半查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。