旋转有序数组的二分查找

比如，数组为: int[] arr = {15， 16， 19， 20，25， 1， 3， 4，5， 7， 10， 14}
查找key = 7
主要思想
每次根据left和right求出mid后，mid的左边为[left, mid]， mid的右边为[mid + 1, right]，这两部分中至少有一个是有序的。
arr[mid]和key比较
(1). arr[mid] == key，返回mid；
(2). arr[mid] < arr[right]，当arr[mid] < key && key < arr[right]，则left = mid + 1，否则 right = mid - 1;
(3). arr[mid] > arr[left]，当arr[mid] > key && key > arr[left]，则right = mid - 1，否则left = mid + 1；

public static int search(int[] arr, int key){
        int left = 0;
        int right = arr.length - 1;
        if (left > right){
            return  -1;
        }

        while (left < right){
            int mid = left + (right - left)/2;
            if (arr[mid] == key){
                return mid;
            }
            //如果前半段有序
            if (arr[mid] > arr[left]){
                //判断Key是否在前半段，如果在，则继续遍历前半段；如果不在，则遍历后半段
                if (arr[mid] > key && key > arr[left]){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            //如果后半段有序
            else if (arr[mid] < arr[right]){
                //判断Key是否在后半段，如果在，则继续遍历后半段；如果不在，则遍历前半段
                if (arr[mid] < key && key < arr[right]){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
        }
        return  -1;
    }