[leetcode 33]Search in Rotated Sorted Array

    //mid 的左边或右边总是有一边是排好序的。
    //若在排好序的里面，则简单搜索，否则就不在该排好序的这边
    public int search(int[] A, int target) {
        int low = 0;
        int high = A.length-1;
        
        while (low < high) {
            int mid = (low + high + 1)/2;
            if (A[mid] == target) return mid;
            if (A[mid] > A[low]) {
                if (target < A[low] || target > A[mid]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            } else {
               if (target < A[mid] || target > A[high]) {
                   high = mid - 1;
               } else {
                   low = mid+1;
               }
            }
        }
        return low < A.length && A[low] == target ? low : -1;
    }