역배열 요소 찾기 - 시간 복잡도 O (lgn)

/**
 * 
 * @author jiadongkai
 * @date  Dec 2, 2011
 *
 */
public class BinSearch {
    
    /**
     *     [1,2,3,4,5]
     *     arr   num index，     -1
     * @param arr
     * @param num
     * @return 
     */
    public static int binSearch(int[] arr, int num){
        int low = 0, high = arr.length-1;
        int mid = 0;
        while(low <= high){
            count++;
            mid = (low+high)/2;
            if(arr[mid] == num) return mid;
            if(arr[mid] < num)//          
                low = mid + 1;
            else                //          
                high = mid - 1;
        }
        return -1;
    }
    
    static int count ;
    
    /**
     * [1,2,3,4,5]->[4,5,1,2,3]
     *              
     * 
     *   mid  ，          。  low/mid-1 mid+1/high
     *           
     *   num       ，
     *              ；  num       ，
     * @param arr
     * @param num
     * @return
     */
    public static int exBinSearch(int arr[], int num){
        int low = 0, high = arr.length-1;
        int mid = 0;
        //    num           
        //   ，              
        boolean flag = false;
        while(low <= high){
            count++;
            mid = (low + high)/2;
            if(arr[mid] == num) return mid;
            if( !flag && (arr[low] <= arr[mid-1])){
                //       
                if((arr[low] <= num) && (num <= arr[mid-1])){
                    // num         
                    System.out.println("      ："+(low)+"  -> "+(mid-1));
                    flag = true;
                    high = mid -1;
                }else{ 
                    // num      
                    low = mid + 1;
                }   
                continue;
            }
            if( !flag && arr[mid+1] <= arr[high]){
                //       
                if( (arr[mid+1] <= num) && (num <= arr[high])){
                    // num         
                    System.out.println("      ："+(mid+1)+" -> "+high);
                    flag = true;
                    low = mid+1;
                }else{
                    // num         
                    high = mid - 1;
                }
                continue;
            }
            //        ，       num        
            if( arr[mid] < num )
                low = mid + 1;
            else
                high = mid - 1;
        }
        return -1;
    }
    
    
    public static void main(String args[]){
        int arr[] = {1,3,5,6,7,8,9,10,22,34,56,67,89,100};
        int arr2[] = {67,89,100,1,3,5,6,7,8,9,10,22,34,56};
        int demo[] = {1,3,5,11,100,56,90,1000};
        for(int i : demo){
            System.out.println("---------  i="+i+"-------------");
            System.out.println( i + " index：" + binSearch(arr, i) );
            System.out.println("    :"+count);
            count=0;
            
            
            System.out.println( i + " index：" +  exBinSearch(arr2, i));
            System.out.println("    :"+count);
        }
        

        
    }
}

//~~~~
-------비교 i=1--------------------1의 index:0 비교 횟수: 3의 질서수조 진입: 3->3 1의 index:3 비교 횟수: 4---------------비교 i=3------------3의 index:1 비교 횟수: 8의 index:1 비교 횟수: 3-------------------비교 i=5--------------------------5의 index:2 비교 횟수: 5의 index:5 비교 횟수: 4----------------비교 i=11-------11의 질서수조 진입 횟수: 7:ndex:-1 비교 횟수: 4 ---------비교 i=100-----------------100의 index:13 비교 횟수: 8 100의 index:2 비교 횟수: 2 -----------------비교 i=56-----------------56의 index:10 비교 횟수: 4 질서수조에 진입: 7 -> 13 56의 index:13 비교 횟수: 4 -----------------------------------비교 i=90-------------90의 index:-1 비교 횟수: 8 90의 index:-1 비교 횟수: 4 ----------------------------------------------------------------비교 횟수: 8 1000 index:-1 비교 횟수: 4