赞
踩
有序的序列,每次都是以序列的中间位置的数来与待查找的关键字进行比较,每次缩小一半的查找范围,直到匹配成功。
实现思路:
(1)将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;
(2)否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
(3)重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
优点:
比较次数少,查找速度快,平均性能好;
缺点:
要求待查表为有序表,且插入删除困难。
使用条件:
查找序列是顺序结构,有序。
public class test01 { public static void main(String args[]) { int [] array={24,56,68,77,79,93,97}; select1(array,93,0,array.length-1); select2(array,93); } /** * 二分查找方法一:递归实现 * @param array */ private static int select1(int[] array,int target,int low,int high) { if(low<0||high>array.length-1||low>high){ System.out.println("有错误!!!"); return -1; } int middle=(low+high)/2; if(array[middle]>target){ return select1(array,target,low,middle-1); }else if(array[middle]<target){ return select1(array,target,middle+1,high); }else{ System.out.println("递归法实现二分查找: "+array[middle]+"的index是:"+middle); return middle; } } /** * 二分查找方法二:非递归实现 * @param array */ private static int select2(int[] array,int target) { int left=0;//左 int right=array.length-1;//右 int middle=0; while(left>=0&&right<array.length&&left<right){ middle=(left+right)/2; if(array[middle]>target){ right=middle-1; }else if(array[middle]<target){ left=middle+1; }else{ System.out.println("非递归法实现二分查找: "+array[middle]+"的index是:"+middle); return middle; } } return -1; } }
分析二分查找法的执行过程。
从上表可以看出N/(2^K)
肯定是大于等于1,也就是N/(2^K)>=1,
我们计算时间复杂度是按照最坏的情况进行计算,也就是是查到剩余最后一个数才查到我们想要的数据,也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的时间复杂度为O(log2N)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。