数据结构中的折半查找是怎么回事?谁能给个具体例子,谢谢了。
发布网友
共2个回答
热心网友
你好 ：
这是我之前写的代码希望能对你有所帮助：
思路：
1. 务必是有序数组 （重点！）
百度百科：（这里偷个懒）半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。
这个代码输入为有序数组 ， 寻找的值
返回：如果找到返回所在坐标，如果没找到返回最小的整型
/***
* @param arr 有序数组
* @param target 查找值
* @return 找到就返回坐标位置，找不到就返回最小值。
* @throws Exception
* @dec 二分查找的非递归算法 ，
* 时间复杂度： o log（n） n n/2 n/4 假设 k次找到 。 n/(2的k次方) 即 2的k次方=n 所以k= logn
*
*/
public static int binarySearch(int arr[], int target) throws Exception {
if(arr==null) {
throw new Exception("ARR IS NULL");
}
if(arr.length<=0) {
throw new Exception("length is illegal");
}
int low = 0;
int high = arr.length-1;
while(low<=high) {
if(target==arr[(low+high)/2]) {
return (low+high)/2;
}else if(target>arr[(low+high)/2]) {
low = (low+high)/2 +1 ;
}else {
high = (low+high)/2 -1;
}
}
return Integer.MIN_VALUE;
}
如果有问题欢迎继续交流指教！
热心网友
http://ke.baidu.com/view/549603.htm?fr=ala0_1_1 比方说一排人按高矮顺序排列 你想找到其中在170CM的，先找最中间一个如果小于170CM那么就把前面一半的人都排除了，只考虑后面一半，反之，就找前面的一半人，再找一半中的中间的和170CM比较，以此类推，直到找到，就停止，如果找到最后没找到就是，没有170CM的人。不知道解释的你懂不懂 希望对你有帮助
