Code & Func

打卡，第16天

失眠的感觉真难受。。。一天都想睡觉，但是却睡不着，sad。

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

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.

在有序的数组中进行查找，显然第一个想到的就是二分查找啦，不过题目给的数组是多了一个限定条件，就是这个数组被rotated了，所以，显然直接用二分查找是不行的。

观察4 5 6 7 0 1 2，我们可以发现如果我们可以找到7这个位置，我们就可以得到两个有序数组，可以进行二分查找，所以一个简单直观的想法就是：

1
if (nums[first] > nums[last]) {
2
    while(last >= 0 && nums[first] > nums[last] && nums[last] < target)
3
        last--;
4
    while(first <= last &&  nums[first] > nums[last] && nums[first] > target)
5
        first++;
6
}
7
//binarySearch

但是这样的时间复杂度就是O(n)了，显然不是我们想要的结果，我们可以对这个转折点进行一次二分查找：

1
if(nums[first] > nums[last]) {
2
    int f= first,l = last;
3
    //找转折点
4
    while(f <= l) {
5
        mid = (f + l)/2;
6
        if (nums[mid] > nums[mid + 1]) break;
7
        else if (nums[mid] > nums[first]) f = mid + 1;
8
        else if (nums[mid] < nums[last]) l = mid;
9
    }
10
    if (target > nums[last]) last = mid;
11
    else if (target < nums[first]) first = mid + 1;
12
    else if (target == nums[first]) return first;
13
    else return last;
14
}
15
//binary Serarch

这样的时间复杂度就是O(2*logn)了。

完整代码：

1
int search(vector<int>& nums, int target) {
2
    int first = 0,last = nums.size() - 1;
3
    int mid;
4

5
    if (last < 0) return -1;
6

7
    if(nums[first] > nums[last]) {
8
        int f= first,l = last;
9
        //找转折点
10
        while(f <= l) {
11
            mid = (f + l)/2;
12
            if (nums[mid] > nums[mid + 1]) break;
13
            else if (nums[mid] > nums[first]) f = mid + 1;
14
            else if (nums[mid] < nums[last]) l = mid;
15
        }
15 collapsed lines
16
        if (target > nums[last]) last = mid;
17
        else if (target < nums[first]) first = mid + 1;
18
        else if (target == nums[first]) return first;
19
        else return last;
20
    }
21
    cout << first << last;
22
    //binary search
23
    while(first <= last) {
24
        int mid = (first + last)/2;
25
        if (nums[mid] == target) return mid;
26
        else if (nums[mid] < target) first = mid + 1;
27
        else last = mid - 1;
28
    }
29
    return -1;
30
}

不过显然这不是最优的方法啦，毕竟要O(2*logn),事实上只需要对二分查找进行修改，就可以直接运用了,恩，这是在dicuss中看到的方法：

1
public int search(int[] A, int target) {
2
    int lo = 0;
3
    int hi = A.length - 1;
4
    while (lo < hi) {
5
        int mid = (lo + hi) / 2;
6
        if (A[mid] == target) return mid;
7

8
        if (A[lo] <= A[mid]) {
9
            if (target >= A[lo] && target < A[mid]) {
10
                hi = mid - 1;
11
            } else {
12
                lo = mid + 1;
13
            }
14
        } else {
15
            if (target > A[mid] && target <= A[hi]) {
8 collapsed lines
16
                lo = mid + 1;
17
            } else {
18
                hi = mid - 1;
19
            }
20
        }
21
    }
22
    return A[lo] == target ? lo : -1;
23
}