Java 实现二分查找\折半查找

        二分查找又称折半查找，优点是比较次数少，查找速度快；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

        该算法要求：

        1、  必须采用顺序存储结构。

        2、  必须按关键字大小有序排列。

        该算法时间复杂度最坏为：O(logn)

         注意点有mid、low、high

        其Java实现代码如下(该代码有缺陷，只是基本实现，有待完善)：

public class BinarySearch ｛

    /**

     * @param args

     */

    public staticvoid main(String[] args) {

       // TODO Auto-generatedmethod stub

       int[] src = {1,3,5,7,8,9};

       System.out.println(binarySearch(src,3));

    }

 

    private staticint binarySearch(int[] src, int i) {

       int low=0;

       int high=src.length-1;

       System.out.println("low is"+low);

       System.out.println("high is"+high);

       while(low<=high){

           int mid = (low+high)/2;

           System.out.println("mid is"+mid);

           if(src[mid]==i){

              return mid;

           }else if(i<src[mid]){

              high=mid-1;

           }else{

              low=mid+1;

           }

       }

       return -1;

    }

}

 

原文：http://blog.csdn.net/woody891/article/details/39230825