/** 
     * 类名：SearchTest.java  
     * 说明: 几种查找方法 
     */  
    public class SearchTest {  
      
        /** 
         * 函数名称：binarySearch 
         * 说明：二分查找 时间复杂度O(logN) 
         */  
        //驱动例程  
          public static <AnyType extends Comparable<? super AnyType>> int  binary(AnyType[] a,AnyType x){  
            return binary(a,0,a.length-1,x);  
          }  
        //递归  
    /*    public static <AnyType extends Comparable<? super AnyType>> int binary(AnyType[] a,int low,int high,AnyType x){ 
            if(low > high) 
                return -1; 
            int mid = (low + high)/2; 
            if(a[mid].compareTo(x) > 0 ) 
                return binary(a,low,mid - 1,x); 
            else if(a[mid].compareTo(x) < 0 ) 
                return binary(a,mid+1,high,x); 
            else return mid; 
             
        }*/  
        //非递归  
        public static <AnyType extends Comparable<? super AnyType>> int binary(AnyType[] a,int low,int high,AnyType x){  
              
            while(low <= high){  
                int mid = (low + high)/2;  
                if(a[mid].compareTo(x) > 0)  
                    high = mid -1;  
                else if(a[mid].compareTo(x) < 0)  
                    low = mid + 1;  
                else  
                    return mid;  
            }  
            return -1;  
        }  
        /** 
         * 函数名称：main  
            * 说明：测试 
         */  
        public static void main(String[] args) {  
            // TODO 自动生成的方法存根  
            Integer[] a = new Integer[]{1,2,3,4,5,6};  
            int x = 3;  
            System.out.println(binary(a,x));  
        }  
      
    }