[LeetCode] Search in Rotated Sorted Array

 

(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.

 

问题描述：给定一个旋转数组，它是一个排序数组通过在一个未知的位置经过旋转而来，需要在该旋转数组中查找一个目标值，如果存在返回它的索引，如果不存在，返回-1。

 

最简单的方法是依次遍历数组，但是这样就没有利用旋转带来的好处。通过旋转可以将一个数组分成两个部分，两个部分都是排好序的，那么，可以将需要查找的值与第一个值进行比较来判断到底是前一部分还是后面一部分。

 

 

 

class Solution {  
public:  
    int search(int A[], int n, int target) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        int i = 0;  
              
        if(target > A[0]) {  
            i = 1;  
            while(i < n && A[i-1] < A[i] && target > A[i])  
                ++i;  
            if(target == A[i])  
                return i;  
            return -1;  
        }  
        else if(target < A[0]) {  
            i = n - 1;  
            while(i > 0 && A[i-1] < A[i] && target < A[i])  
                --i;  
            if(target == A[i])  
                return i;  
            return -1;  
        }  
        else {  
            return 0;  
        }  
    }  
};  

 

 

这是一种比较直观而且代码写很好写的方法，还有另外一种就是比较常用的二分法。

 

使用二分法的话，由于数组是经过旋转的，因此，当target与A[mid]进行比较之后，不能和一般的二分法一样直接将left或者right改变，需要进行讨论。

 

首先，当target大于A[mid]时，要判断旋转点的范围，这通过将A[mid]与A[left]进行比较，当A[mid]大于或者等于A[left]（这里不可能等于，因为这题假设没有重复元素）时，旋转点在mid与right之间（包括mid），那么如果target存在的话，必定是在mid与right之间，将left置为mid+1；当A[mid]小于A[left]时，旋转点就在left与mid之间，又因为target>A[mid]，此时无法确定target在哪个区间，因此将target与A[right]进行比较，如果target>A[right]，那么target在left与mid之间，如果target<A[right]，那么target在mid与right之间，如果target==A[right]，返回right。

 

当target小于A[mid]时，与上面类似。

 

 

class Solution {  
public:  
    int search(int A[], int n, int target) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        int left = 0, right = n - 1;  
        int mid = 0;  
              
        while(left <= right) {  
            mid = (left + right) / 2;  
            if(target > A[mid]) {  
                if(A[mid] >= A[left]) {  
                    left = mid + 1;  
                }  
                else {  
                    if(target > A[right]) {    
                        right = mid - 1;  
                    }  
                    else if(target < A[right]) {  
                        left = mid + 1;  
                    }  
                    else  
                        return right;  
                }  
            }  
            else if(target < A[mid]) {  
                if(A[mid] >= A[left]) {  
                    if(target > A[left]) {  
                        right = mid - 1;  
                    }  
                    else if(target < A[left]){  
                        left = mid + 1;  
                    }  
                    else  
                        return left;  
                }  
                else {  
                    right = mid - 1;  
                }  
            }  
            else {  
                return mid;  
            }  
        }  
              
        return -1;  
    }  
};  

 

 

补充：软件开发 , C++ ,