Rotated Sorted Array旋转排序数组相关题

1.什么是Rotated Sorted Array

在leetcode相关题目中，对Rotated Sorted Array相关的定义为：
整数数组 nums 按升序排列，数组中的值互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

通俗地讲，旋转数组中没有相等的数值，且该数组可以被分为连续的两部分，这两部分均按升序排列。

2.寻找旋转排序数组中的最小值

leetcode中153题，就是寻找旋转数组中的最小值。
一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

从图中不难看出，假设数组中最后一个元素为x,那么最小值右侧的元素一定都比这个元素小，而最小值左侧元素都比这个值大。

进行二分查找时，假设左右边界分别为low, high，中间为pivot。

1. nums[pivot] < nums[high]，说明nums[pivot]是最小值右侧的元素，因此忽略二分查找的右半部分。
   
   2.nums[pivot] > nums[high]，说明nums[pivot]是最小值左侧的元素，因此忽略二分查找的左半部分。
   
   因为数组元素不重复，只要当前区间长度不为1，pivot不会与high重合。而当区间长度为1时，说明二分查找已经结束。

int run() {
    int nums[] = {4,5,6,7,0,1,2};
    int n = sizeof(nums)/ sizeof(nums[0]);
    int left = 0, right = n - 1;
    while(left < right) {
        int pivot = (left + right) / 2;
        if (nums[pivot] < nums[right]) {
            right = pivot;
        } else {
            left = pivot + 1;
        }
    }
    return nums[left];
}

注意上面代码终止时，right刚好与left相等。

3.搜索旋转排序数组

跟上面类似的题是leetcode 33题，在一个旋转排序数组中进行搜索。

解题思路与上面类似，首先找出最小值点，就可以将数据分为有序的两部分，然后看nums[0]与target的大小。如果nums[0]<target，说明要在左半部分进行二分查找。反之在右半部分进行二分查找。

int run2() {
    int nums[] = {4,5,6,7,0,1,2};
    int n = sizeof(nums)/sizeof(nums[0])-1;
    int left = 0, right = n-1, target = 0;
    while(left < right) {
        int pivot = (left + right) / 2;
        if (nums[pivot] < nums[right]) {
            right = pivot;
        } else {
            left = pivot + 1;
        }
    }
    
    int curleft = 0, curright = 0;
    if (nums[0] < target) {
        curleft = 0, curright = left - 1;
    } else {
        curleft = left, curright = n-1;
    }
    while(curleft <= curright) {
        int mid = (curleft + curright) / 2;
        if (nums[mid] < target) {
            curleft = mid + 1;
        } else if (nums[mid] > target) {
            curright = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}