Leetcode and Lintcode

Search in Rotated Sorted Array

Problem:

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.

Example
For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge
O(logN) time

lintcode link
Leetcode link

My Solution:

Use binary search to find the match.
There are some notable tips:

  • Check the start point first (at the left or right side of mid), then assume the target on the consecutive segment.
  • While loop condition: left != right
  • After the while loop, we should add “if (nums[left] == target) return left;”
  • The if condition “nums[mid] >= nums[left]” should contain the equal sign

The time complexity is O(log n).

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
 /*************************************************************************                                                                                                          
  > File Name: SearchInRotatedArray.java
  > Author: Yao Zhang                                                                                                                                                          
  > Mail: psyyz10@163.com       
  > Created Time: Thu 29 Oct 15:26:17 2015
  ************************************************************************/
                                       
public class SearchInRotatedArray{  
    if (nums == null || nums.length == 0)
            return -1;
        
        int left = 0;
        int right = nums.length - 1;
        
        while (left != right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            
            if (nums[mid] >= nums[left]){
                if (target >= nums[left] && target < nums[mid])    
                    right = mid - 1;
                else 
                    left = mid + 1;
            } else {
                if (target > nums[mid] && target <= nums[right])
                    left = mid + 1;
                else 
                    right = mid - 1;
            }
        }
        
        if (nums[left] == target) return left;
        
        return -1;                  
    }                                  
}

Related Problem:
Search in Rotated Sorted Array II