3.4 Search in Rotated Sorted Array

Description

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.

Method

binary search if we use an axis coordinates to represents the array. Since it has been rotated, it drops two lines the mid in the array maybe in the first line, or second line. we should decided where is the mid value firstly, and then compare it with the target to narrow the space for next search

Time and Space Complexity

o(logn)

Code

public class Solution {

    public int search(int[] nums, int target) {
       if (nums == null || nums.length == 0){
           return -1;
       }
       int start = 0;
       int end = nums.length - 1;

       while (start + 1 < end){
             int mid = (end - start) / 2 + start;
             //System.out.println("mid:" + mid);
             if (target == nums[mid]) {
                 return mid;
             } else if (nums[mid] > nums[end]){
                    if (target <= nums[mid] && target > nums[end]){
                        end = mid;
                    } else {
                        start = mid;
                    }
             } else {
                    if (target >= nums[mid] && target <= nums[end]){
                        start = mid;
                    } else {
                        end = mid;
                    }
             }
      }
       if (nums[start] == target){
           return start;
       }
       if (nums[end] == target){
           return end;
       }
       return -1;
}

}