在旋转过的有序数组中寻找目标值

题目：

有一个长度为 n 的按严格升序排列的整数数组 nums,

在实行 search 函数之前，在某个下标 k 上进行旋转，使数组变为

[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。

给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其

下标（从0开始计数），如果不存在请返回-1。

示例：

输入：[6,8,10,0,2,4],10

返回值：2

输入：[6,8,10,0,2,4],3

返回值：-1

输入：[2],1

返回值：-1

解题思路：

二分查找：

首先通过mid = (left + right) / 2找到数组的中间数，由于该数组是由有序数组旋转得到的，所以mid的左右必有一侧有序。在有序的区间内，接着利用二分查找。

假设左侧有序，则判断目标值是否在该区域内；若不在该区域内，说明目标值在右侧区域，再次利用二分查找，将右侧区域分为两个部分，其中必有一侧是有序的。

依次反复查找，左右侧查找同理可得。

代码示例：

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @param target int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int search(int* nums, int numsLen, int target ) {
    // write code here
    int left = 0,right = numsLen - 1;
    int mid = 0;
    while(left <= right){
        mid = (right - left) / 2 + left;
        if(nums[mid] == target) 
        return mid;
        if (nums[0] < nums[mid]) { 
            if(target >= nums[0] && target <= nums[mid]) { 
                right = mid - 1;
            } else { 
                left = mid + 1;
            }
        } else { 
            if (target >= nums[mid] && target <= nums[numsLen - 1]) {
                left = mid + 1;
            } else { 
                right = mid - 1;
            }
        }
    }
    return -1;
}