Skip to content

Instantly share code, notes, and snippets.

@hsaputra
Last active November 10, 2018 17:41
Show Gist options
  • Save hsaputra/d2cc3a1fbe8cbb106b0d98679272d8c3 to your computer and use it in GitHub Desktop.
Save hsaputra/d2cc3a1fbe8cbb106b0d98679272d8c3 to your computer and use it in GitHub Desktop.
33. Search in Rotated Sorted Array
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;
}
}
@hsaputra
Copy link
Author

hsaputra commented Nov 8, 2018

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

@hsaputra
Copy link
Author

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); 
    } 
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment