66、二分-搜索旋转排序数组

思路：

        不断二分，首先判断左侧有序还是右侧有序，如果左侧有序那么就在左侧寻找，如果右侧有序那就在右侧寻找。假设左侧有序，那就判断目标值在不在左侧，如果在左侧继续左侧二分。如果不在左侧，那么在右侧继续二分再去寻找。

突出点不断二分，然后在有序部分寻找。有序部分没找到，那就在二分再在有序部分寻找。

代码如下：

public class Solution {

  public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    return process(nums, 0, nums.length - 1, target);
}

private int process(int[] nums, int L, int R, int target) {
    if (L > R) {
        return -1; // 递归结束条件
    }

    int mid = L + (R - L) / 2;
    if (nums[mid] == target) {
        return mid; // 找到目标值
    }

    // 判断左半部分是否有序
    if (nums[L] <= nums[mid]) {
        // 再判断目标值是否在这个有序的部分中
        if (target >= nums[L] && target < nums[mid]) {
            return process(nums, L, mid - 1, target); // 目标在左侧有序部分，继续在这部分查找
        } else {
            return process(nums, mid + 1, R, target); // 目标不在左侧有序部分，转到右侧查找
        }
    } else {
        // 如果左半部分不是有序的，那么右半部分必定是有序的
        // 判断目标值是否在右侧的有序部分中
        if (target > nums[mid] && target <= nums[R]) {
            return process(nums, mid + 1, R, target); // 目标在右侧有序部分，继续在这部分查找
        } else {
            return process(nums, L, mid - 1, target); // 目标不在右侧有序部分，转到左侧查找
        }
    }
}

}