首页 > 代码库 > leetcode--Search in Rotated Sorted Array

leetcode--Search in Rotated Sorted Array

2024-07-07 09:26:20   225人阅读

Suppose a sorted array 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.

?
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
public class Solution {
   /**
     * modified the binary search.<br>
     *when the array is rotated, we first find the minimum and then do binary search in appropriate subarray.<br>
     * @param A  --Integer array, search in this array
     * @param target --int, searched number  *
     * @return int. If the target is found, return the index, otherwise return -1.
     * @author Averill Zheng
     * @version 2014-06-05
     * @since JDK 1.7
     */
    public int search(int[] A, int target) {
        int length = A.length, index = -1;
        if(length > 0){
            int tempIndex = 0;
            if(A[0] <= A[length - 1]) //normal order
                tempIndex = Arrays.binarySearch(A, target);
                //index = (tempIndex >= 0) ? tempIndex : -1;
            else{
                //find the min first
                int min = findMin(A, 0, length - 1);
                 
                if(target >= A[0])
                    tempIndex = Arrays.binarySearch(A, 0, min, target);
                else
                    tempIndex = Arrays.binarySearch(A, min, length, target);
            }
            index = (tempIndex < 0) ? -1 : tempIndex;
        }
        return index;  
    }
    public  int findMin(int[] A, int i, int j){
        int min = i, left = i, right = j;
        if(A[i] > A[j]){
            while(left < right - 1){
                int mid = left + (right - left) / 2;   
                if(A[left] < A[mid])
                    left = mid;            
                else
                    right = mid;           
            }
            min = (A[left] < A[right])? left : right;
        }
        return min;
    }
}

　

leetcode online judge is also accepted the code if we use the linear search method to find the minimum as follows:

?
1
2
3
4
5
6
7
8
9
10
public int findMin(int[] A, int i, int j){
    int left = i, right = j;
    while(left < right){
        if(A[left] > A[right])
            ++left;
        else
            --right;
    }
    return left;
}

　　

　


联系
我们