0033 搜索旋转排序数组

算法思路

考虑到题目要求要求以 \(O(\log n)\) 的时间复杂度在数组中找到特定元素。同时，题目给出的数组本质上是有序的，相当于一个不重复的递增数组，在某一位置进行了切割并重新拼起来。

根据以上信息，显然考虑使用二分查找。关键在于如何进行二分查找，这道题我想到的方法是查找两次：由于数组的特性，我们可以先通过第一次二分查找获得数组的最大值及其索引。 随后，根据最大值索引将数组视作两个不相交的递增数组，并进行第二次二分查找获得题目所求。

代码实现

search-in-rotated-sorted-array.c

int getMax(int* nums, int left, int right, int a) {
    if (left == right) {
        return left;
    } else if (left + 1 == right) {
        return nums[left] > nums[right] ? left : right;
    }
    int mid = nums[(left + right) / 2];
    if (mid > a) {
        return getMax(nums, (left + right) / 2, right, a);
    } else {
        return getMax(nums, left, (left + right) / 2, a);
    }
}

int getIndex(int* nums, int left, int right, int target) {
    if (left >= right && nums[right] != target) {
        return -1;
    }
    int mid = nums[(left + right) / 2];
    if (mid > target) {
        return getIndex(nums, left, (left + right) / 2 - 1, target);
    } else if (mid < target) {
        return getIndex(nums, (left + right) / 2 + 1, right, target);
    } else {
        return (left + right) / 2;
    }
}

int search(int* nums, int numsSize, int target) {
    int a = nums[0];
    if (target == a)
        return 0;
    int maxIndex = getMax(nums, 0, numsSize - 1, a);
    if (target > a) {
        return getIndex(nums, 1, maxIndex, target);
    } else {
        return getIndex(nums, maxIndex + 1, numsSize - 1, target);
    }
}

• 易错：对于第二次二分查找 getIndex 函数，由于 target 不一定存在，需要进行 if (left >= right && nums[right] != target) 判断。并且由于 left >= right，应使用 right 作为数组下标避免越界。

UPDATE

阅读题解后，不免感叹自身实力欠缺，竟然绕了一个大弯去解决此题。可能是“将未知问题转化为已知问题”的想法过于强烈，以至于我采用了两次二分查找去解决此问题，试图将数组变成最令人舒适的简单递增数组。

但实际上，一次二分查找即可无痛解决问题。因为我们将数组拆分为两部分后，必然至少有一边是有序的。而在不断递归二分查找的过程中，必然存在一次拆分，使得我们的目标值出现在有序数组的取值区间中。以上，即说明了一次二分查找便可解决问题。

search-in-rotated-sorted-array.c

int search(int* nums, int numsSize, int target) {
    int n = numsSize;
    if (n == 0) {
        return -1;
    }
    if (n == 1) {
        return nums[0] == target ? 0 : -1;
    }
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) return mid;
        if (nums[0] <= nums[mid]) {
            if (nums[0] <= target && target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[n - 1]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    return -1;
}