L33 Search in Rotated Sorted Array

Binary Search

Problem

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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

• It is ascending order, but it is rotated

• Imagine theres is a graph like below, left is the original array, right is already rotated.

  

Solution:

• Based on the basic binary search conditions, there are two more conditions should be considered.

  • if array[left] < array[mid], left and mid should be at the same area, area 1 or area 2. Whether the they are at area 1 or area 2, if the target is between array[left] and array[mid], right should be moved, otherwise, move the left.

  • if array[left] > array[mid], this means left is in area 1, and mid is in area 2. In this case, if the target is between array[mid] and array[right], we should move left, otherwise, move the right.

• Since left - 1 < right is not easy to do the post check, so we use left <= right

public int search (int[] array, int target){
    if(array == null || array.length == 0) return -1;
    int left= 0, right = array.length - 1;
    
    while(left <= right){
        int mid = left + (right - left) /2;
        if(array[mid] == target) return mid;
        if(array[left] == target) return left;
        if(array[right] == target) return right;
        
        if(array[left] < array[mid]){
            if(target > array[left] && target < array[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }else if(array[left] > array[mid]){
            if(target > array[mid] && target < array[right]){
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }
    }
    return - 1;
}