题目解析

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,3,4,5,6] might become [5,6,0,1,2,3,4]).
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).

思路类比二分， 变种，比较中位数和左右两个边界大小， 能确定哪半边是有序，哪半边是转置。再比较大小确target再哪半边，有序的采用二分查找，转置的回到了初始问题

排序数组中超找某个元素，二分查找较快速。 题目有点改动是此排序数组经过轮转， 其实本质还是按照二分查找的思路来

分析步骤

1、轮转的递增排序数组，有个特点， 我们取中位数后，必定有一段是单调增，另一段是轮转有序
2、那么就是一个初始条件缩减问题， 如果目标数在单调增里面，那么二分查找，如果不在，回到了1流程初始问题
3、考虑边界条件和循环退出条件

代码演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class A33RotatedSortedArray {

    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        if (nums.length == 0) {
            return -1;
        }
        if (target < nums[start] && target > nums[end]) {
            return -1;
        }
        if (target == nums[start] && start == end) {
            return start;
        }
        while (start <= end) {
            int index = (start + end) / 2;
            int tmp = nums[index];
            if (tmp == target) { // 找到目标
                return index;
            }
            if (tmp <= nums[end]) {
                if (target >= tmp && target <= nums[end]) { // target 在有序右侧
                    return searchSecond(nums, target, index, end);
                } else { // target在转置左侧，重新调整右边界
                    end = index - 1;
                }
            } else {
                if (target >= nums[start] && target <= tmp) { // target 在有序左侧
                    return searchSecond(nums, target, start, index);
                } else { //// target在转置左侧，重新调整左边界
                    start = index + 1;
                }
            }
        }
        return -1;
    }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @param start
     * @param end
     * @return
     */
    private static int searchSecond(int[] nums, int target, int start, int end) {
        while (start <= end) {
            if (target < nums[start] || target > nums[end]) {
                return -1;
            }
            int index = (start + end) / 2;
            int tmp = nums[index];
            if (tmp == target) {
                return index;
            }
            if (target < tmp) {
                end = index - 1;
            } else {
                start = index + 1;
            }
        }
        return -1;
    }

代码文件：
A33RotatedSortedArray.java

总结

  • 如果前置条件变化，可能的一种是某些思路的理解演进或者举一反三。 还有一类是思考逻辑递进式

版权声明：本文为博主原创文章，未经允许不得转载。