查找算法之折半查找

 折半查找是我很喜欢的一种查找方式，它代码简单，查询效率很高，时间复杂度是0(log2n).
折半查找是在一个有序的元组中查找元素，它通过关键词与中间值的比较，来查找相关的元素。如果关键词比中间值大，那么就在元组的后半部分查找，反之亦然。很显然，折半查找是基于递归思想的。下面先贴出其递归代码的实现

public class BinarySearch {
    //折半查找，应确保传进来的数组是有序的
    static int binarySearch(int[] n,int num ,int low,int high){

     if(low<=high){
         int mid = (low+high)/2;
         if(n[mid] == num)
             return mid;
         else if(n[mid] > num)
          return       binarySearch(n,num,low,mid-1); //后半部分查找
         else
            return  binarySearch(n,num,mid+1,high); //前半部分递归查找
     }

        return -1;
    }
    public static void main(String[] arg){
        int n[]={1,2,3,3,3,4,5,6};
        for(int i=0;i<=8;i++)
        {

            int flag = binarySearch(n,i,0,n.length-1);
            System.out.println("在数组中查找"+i+" 位置是："+flag);
        }


    }

}

运行结果如下
在数组中查找0 位置是：-1
在数组中查找1 位置是：0
在数组中查找2 位置是：1
在数组中查找3 位置是：3
在数组中查找4 位置是：5
在数组中查找5 位置是：6
在数组中查找6 位置是：7
在数组中查找7 位置是：-1
在数组中查找8 位置是：-1
我们知道，递归是很消耗栈空间的，虽然递归的形式简单，易懂，但是如果可以，我们尽量都要求用非递归的形式实现算法，下面是其的非递归形式。

public class BinarySearch {
    //折半查找，应确保传进来的数组是有序的
    static int binarySearch(int[] n,int num){
        int low = 0;
        int high = n.length-1;
        while(low<=high){
            int mid = (low+high)/2; // 从中间位置开始找
            if(n[mid] == num)
                return mid;
            else if(n[mid]<num){
                low=mid+1;
                }else
                {
                    high = mid-1;
                }
        }

        return -1;
    }
    public static void main(String[] arg){
        int n[]={1,2,3,3,3,4,5,6};
        for(int i=0;i<=8;i++)
        {

            int flag = binarySearch(n,i);
            System.out.println("在数组中查找"+i+" 位置是："+flag);
        }


    }

}

好了，其实，折半查找也是有它的缺点的，从上面的例子可以看出，在元组{1,2,3,3,3,4,5,6}中，查找元素3时，只是输出了第一次找到的结果，另外折半查找要求元组的元素是有序的，查找的结果才是正确的。不过总的来说，折半查找还是一种性能卓越的查找算法。