1. 题目描述

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

2. 解题

在Leetcode上看到这个很有意思的题，在旋转过的有序数组中用O(logN)的时间复杂度找一个数，下面我尝试用我的方法解这道题。

方法的本质就是分情况。可知一个旋转后的有序数组可以分为两个部分，大致如下图所示，相当于横坐标为数组索引，纵坐标为数组值，然后把每个点连成线

暂且把左半部分称为左臂，右半部分称为右臂。现在开始分情况，可知任意一个旋转后的有序数组表示成上图的形式，有以下三种情况：

• 左臂比右臂长
• 右臂比左臂长
• 左臂右臂等长

那么现在仿照普通的二分查找，设左端点为left，右端点为right，然后取一个mid。可知对于上面第一种情况，mid一定落在左臂上。对于第二种情况，mid一定落在右臂上。对于第三种情况，由于C语言数组下标从0开始，所以mid也一定落在左臂上。

然后用代码判断mid是在左臂上还是右臂上，如果mid表示的值大于等于left表示的值，则mid在左臂上，否则mid在右臂上。

之后继续仿照二分查找，判断target在mid的左边还是右边。这时候分情况的作用就体现出来了。对于上面第一种情况，如果target >= arr[left] && target <= arr[mid]则target在mid左边，所以收缩right，否则收缩left。对于第二种情况，如果target >= arr[mid] && target <= arr[right]则target在mid右边，所以收缩left，否则收缩left。

然后重复上述步骤直到最终找到target。

3. 代码

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] >= nums[left]) {  // mid落在左臂
            if (target >= nums[left] && target <= nums[mid]) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        else if (nums[mid] < nums[left]) {  // mid落在右臂
            if (target >= nums[mid] && target <= nums[right]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
    }

    return -1;
}