33. Search in Rotated Sorted Array

gistfile1.txt

class Solution {
    // [4,5,6,7,0,1,2,3]
    // [6,7,0,1,2,3,4,5]
  public int search(int[] nums, int target) { 
    if (nums == null || nums.length == 0) {
      return -1;
    }
    
    final int numsLen = nums.length;
      
    int lo = 0;
    int hi = numsLen - 1;
    
    while (lo < hi) {
      
      int mid = (lo + hi)/2;
      
      if (nums[mid] == target) {
        return mid;
      }    
      
      // check if first half is sorted
      if (nums[lo] <= nums[mid]) {
        if (target >= nums[lo] && target < nums[mid]) {
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      } else {
        // if not the other one must be
        if (target <= nums[hi] && target > nums[mid]) {
          lo = mid  + 1;
        } else {
          hi = mid - 1;
        }        
      }
    }
    
   return nums[lo] == target ? lo : -1; 
  }
}

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 1:

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

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

class Solution {
    // [4,5,6,7,0,1,2,3]
    // [6,7,0,1,2,3,4,5]
  public int search(int[] nums, int target) { 
    if (nums == null || nums.length == 0) {
      return -1;
    }
      
    final int n = nums.length;
    int pivot = findPivot(nums, 0, n-1); 
        
    // If we didn't find a pivot, then  
    // array is not rotated at all 
    if (pivot == -1)  {
      return binarySearch(nums, 0, n-1, target); 
    } else {
        
      // If we found a pivot, then first  
      // compare with pivot and then 
      // search in two subarrays around pivot 
      if (nums[pivot] == target) 
        return pivot; 
      
      if (nums[0] <= target) {
        return binarySearch(nums, 0, pivot-1, target); 
      } else {
        return binarySearch(nums, pivot+1, n-1, target); 
      } 
    }
  }
       
    /* Function to get pivot. For array  
       3, 4, 5, 6, 1, 2 it returns 
       3 (index of 6) */
    private int findPivot(int arr[], int low, int high) { 
      // base cases 
      if (high < low)   
        return -1; 
      if (high == low)  
        return low; 
         
      int mid = (low + high)/2;   
      
      if (mid < high && arr[mid] > arr[mid + 1]) 
        return mid; 
      if (mid > low && arr[mid] < arr[mid - 1]) 
        return (mid-1); 
      if (arr[low] >= arr[mid]) 
        return findPivot(arr, low, mid-1); 
      
      return findPivot(arr, mid + 1, high); 
    } 
       
    /* Standard Binary Search function */
    private int binarySearch(int arr[], int low, int high, int key) 
    { 
       if (high < low) 
           return -1; 
         
       /* low + (high - low)/2; */       
       int mid = (low + high)/2;   
       if (key == arr[mid]) 
           return mid; 
       if (key > arr[mid]) 
           return binarySearch(arr, (mid + 1), high, key); 
       return binarySearch(arr, low, (mid -1), key); 
    } 
}