33. Search in Rotated Sorted Array

题目描述和难度

题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

题目难度：中等。
英文网址：33. Search in Rotated Sorted Array 。
中文网址：33. 搜索旋转排序数组。

思路分析

求解关键：这道题还是很有意思的，完成这道题可以帮助我们明确解决这类问题的一些细节。虽然题目给出的数组不是有序的数组，但是是“部分有序”的，只有 1 个间断点，所以依然可以使用二分查找算法。

“假设数组中不存在重复的元素”这句话很关键，我们可以少考虑下面两种特殊的用例。

用例1：1 2 1 1 1 1 找 2。

用例2：1 1 1 1 2 1 找 2。

二分法总是期望通过每一次的操作能够少考虑一部分的情形。考虑完特殊情况，其余的就交给 else。

有部分解释放在了代码的注释中。

参考解答

参考解答1

public class Solution {

    // 不管怎么分，都一定有一边是递增序列
    // 另一边是一个规模更小的旋转数组

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

        int left = 0;
        int right = len - 1;
        // 特别注意：这里是等于
        // 特别注意：这里是等于
        // 特别注意：这里是等于
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 这里有一个坑，那就是
            // mid 有可能和 left 相等，所以分类标准这样
            // nums[left] < nums[mid] 不能用这个判断
            if (nums[mid] > nums[right]) {
                // 此时旋转点在右边
                // 6 7 8 9 1 2
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // 此时旋转点在左边
                // 6 7 1 2 3 4 5 6
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        int target = 3;
        Solution solution = new Solution();
        int search = solution.search(nums, target);
        System.out.println(search);
    }
}

参考解答2

public class Solution2 {

    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        int left = 0;
        int right = len - 1;
        // 注意：这里是等于
        while (left <= right) {
            // 这里取 right - left + 1 说明是向上取整
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] < nums[mid]) {
                // 6 7 8 9 1 2
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                assert nums[left] >= nums[mid];
                // 6 7 1 2 3 4 5
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0033-search-in-rotated-sorted-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。