java二分法查找

二 分查找是一种高效率线性表的查找算法。在查找时必须将线性表中的关键字排好序。基本思路是：先确定线性表的中间位置 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 stubint[] 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。

1 楼 于风华 2012-09-12 first+last可能越界，改成first+（last-first）/2除二 最保险 2 楼 mcdowell123 2012-09-12 这个还用自己写吗 java 都封装好了 java.util .Collections 类中就有 binarySearch 方法 直接用就好了、
3 楼 于风华 2012-09-20 binarySearch mcdowell123 写道这个还用自己写吗 java 都封装好了 java.util .Collections 类中就有 binarySearch 方法 直接用就好了、

当然可以用这个，但是有时候自己写的东西自己心里有谱 哈哈 同时也可锻炼一下嘛