java二分法查找
- - ITeye博客二 分查找是一种高效率线性表的查找算法. 在查找时必须将线性表中的关键字排好序. 基本思路是:先确定线性表的中间位置 mid=(first+last)/2;比较所要查找的关键字 key与中间位置的关键字的大小,如果比key和mid.key相等则返回; key比mid.key大(假定为升序)这所要查找的关键字在mid和last之间;否则在first与mid之间.
二 分查找是一种高效率线性表的查找算法。在查找时必须将线性表中的关键字排好序。基本思路是:先确定线性表的中间位置 mid=(first+last)/2;比较所要查找的关键字 key与中间位置的关键字的大小,如果比key和mid.key相等则返回; key比mid.key大(假定为升序)这所要查找的关键字在mid和last之间;否则在first与mid之间。继续按照上面方法查找中间元素,直到 找到为止。
具体实现如下
public class BinarySearch { public BinarySearch() { super(); } /** * Java二分法查找 * @param a * @param key * @return */ public static int binarySearch(int[] a, int key) { if(a.length==0) return -1; //开始位置 int first = 0; //结束位置 int last = a.length-1; //中间位置 int mid; //如果开始时,小于则结束. while(first<=last) { mid = (first+last)/2; //如果等于key,返回这个数在数组中的位置. if(a[mid]==key) return mid; //如果大于key,则在左边. if(a[mid]>key) last = mid-1; //如果小于key,则在右边 if(a[mid]<key) first = mid+1; } return -1; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] a={1,3,4,5,8,7,9,11,15}; System.out.println(binarySearch(a,9)); } }
这样就打印出了所要查找的关键字所在位置的下标。对二分查找求平均查找长度二分查找的过程相当与一棵二叉排序树,所以总节点数为n=2^h- 1,h=Log2 (n+1)。 第i层上的节点数为2^(1-1);在等概率的情况下,平均查找长度ASL=Log2 (n+1)-1。