自己解法

因为要求时间复杂度是O(logN),加上数组是部分有序的，肯定是二分查找的。于是根据mid是在左侧序列，还是右侧序列，然后结合left和right位置的数值和target做对比，不断收缩查找范围。

class Solution {

    public int search(int[] nums, int target) {

        if (nums.length == 0) {

            return -1;

        }

        if (nums.length == 1 && nums[0] == target) {

            return 0;

        }

        int left = 0;

        int right = nums.length - 1;

        while (left < right) {

            int mid = (left + right) / 2;

            if (nums[mid] == target) {

                return mid;

            }

            if (nums[left] == target) {

                return left;

            }

            if (nums[right] == target) {

                return right;

            }

            // 两个可能会出现无法收敛的情况

            if (right - left <= 1) {

                return -1;

            }

            // mid在左侧情况

            if (nums[mid] > nums[left]) {

                if (nums[mid] < target) {

                    left = mid;

                } else {

                    if (nums[left] > target) {

                        left = mid;

                    } else {

                        right = mid;

                    }

                }       

            } else {

                // mid在右侧

                if (nums[mid] > target) {

                    right = mid;

                } else{

                    if (nums[right] > target) {

                        left = mid;

                    } else {

                        right = mid;

                    }

                }

            }

        }

        return -1;        

    }

}

官方解法

思路类似，但官方解法更简洁，同样是找mid的位置，看mid的左侧是有序的，还是右侧是有序的，然后判断target是否在有序区间，不在有序区间，就在另一半空间中，判断更加简洁，并且mid已经判断不是target的情况下，再次确定区间用mid - 1和mid + 1就好，解决收敛问题。

class Solution {

    public int search(int[] nums, int target) {

        if (nums.length == 0) {

            return -1;

        }

        if (nums.length == 1 && nums[0] == target) {

            return 0;

        }

        int left = 0;

        int right = nums.length - 1;

        while (left <= right) {

            int mid = (left + right) / 2;

            if (nums[mid] == target) {

                return mid;

            }

            // mid在左侧情况，说明左侧是有序的

            if (nums[mid] >= nums[left]) {

                if (nums[mid] > target && nums[left] <= target) {

                    right = mid - 1;

                } else {

                    left = mid + 1;

                }       

            } else {

                // mid在右侧,说明右侧是有序的

                if (nums[mid] < target && target <= nums[right]) {

                    left = mid + 1;

                } else{

                    right = mid -1;

                }

            }

        }

        return -1;        

    }

}