LeetCode 33. Search in Rotated S

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

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

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

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

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

示例 :

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

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

思路:

• 在一个旋转后的数组中查找是否存在某元素的索引,非常适合使用二分法查找(题目也给了暗示)
• 可以通过区分元素所在区间(旋转后的序列前半段或后半段)
• 也可以通过直接在二分查找中判定

代码1:

• 效率不高,思路简单

    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0)
            return -1;
        int i = 0, j = len - 1, start = 0;
        //获取旋转节点
        for (int k = 0; k < len - 1; k++) {
            if (nums[k] > nums[k + 1])
                start = k + 1;
        }
        //重置target所在区间
        if (nums[0] <= target) {
            j = start - 1;
            if (start == 0)
                j = len - 1;
        } else {
            i = start;
        }
        //二分法查找
        int mid = -1;
        while (i <= j) {
            mid = (i + j) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) {
                j = mid - 1;
                mid = (i + j) / 2;
            } else {
                i = mid + 1;
            }
        }
        return -1;
    }

代码2:

• 效率排行中非常靠前的解法,在普通的二分查找中加入区间判断

    public int searchBest(int[] nums, int target) {
        int begin = 0;
        int end = nums.length - 1;
        if (begin > end)
            return -1;
        while (begin <= end) {
            int mid = begin + (end - begin + 1) / 2;
            if (nums[mid] == target)
                return mid;
            if (nums[mid] > nums[begin]) {
                //在二分查找中,对target所在区间进行重置
                if (nums[begin] <= target && nums[mid] > target) {
                    end = mid - 1;
                } else {
                    begin = mid + 1;
                }
            } else {
                if (nums[end] >= target && nums[mid] < target) {
                    begin = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }

总结

1. 本题较为简单,考验读题能力与二分查找法的运用