LeetCode:Search in Rotated Sorted Array

Search in Rotated Sorted Array:http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
关键点:旋转前数组有序,无重复元素。


参考解法:
由于旋转前数组有序,故旋转后,数组被分为两个有序的子区间(无旋转时为一个有序区间)。
算法同样采用折半查找的思想进行搜索,但上下界firstlast的更新相比常规的折半查找略微复杂。
在下面的高亮行11进行判断时,若if判断成立,由旋转前数组有序的条件可知firstmid之间的元素都有序(在一个有序子区间中),故在高亮行12时若if仍成立,则target[first,mid)之间,否则在[mid+1,last)之间。
同上述分析,在高亮行18时若if成立,则target[mid+1,last)之间。

// 时间复杂度O(log n),空间复杂度O(1)
class Solution {
public:
    int search(int A[], int n, int target) {
        int first = 0;
        int last = n;
        while (first != last) {
            int mid = (first+last)/2;
            if (target == A[mid])
                return mid;
            if (A[first] <= A[mid]) {
                if (A[first] <= target && target < A[mid])
                    last = mid;
                else
                    first = mid+1;
            }
            else {
                if (A[mid] < target && target <= A[last-1])
                    first = mid+1;
                else
                    last = mid;
            }
        }
        return -1;
    }
};

LeetCode:Search in Rotated Sorted Array》上有1条评论

  1. Pingback引用通告: LeetCode:Search in Rotated Sorted Array II | 张学程

发表评论

电子邮件地址不会被公开。