Search in Rotated Sorted Array

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

OPTION 1:

class Solution {
    public int search(int[] nums, int target) {
        
        
        for(int i=0;i<nums.length;i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
}  

Here, it is easiest solution. Traverse the entire array, if num[i] is equal to target, return index position.
Else return -1.

Time Complexity: O(n)

OPTION 2:

class Solution {
    public int search(int[] nums, int target) {
       
        int result = search(nums, 0, nums.length-1, target);
        return result;
       
    }
   
      static int search(int num[], int low, int high, int target)
    {
        if (low > high) 
            return -1;
       
        int mid = (low+high)/2;
        if (num[mid] == target)
            return mid;
       
        if (num[low] <= num[mid])
        {
          
            if (target >= num[low] && target <= num[mid])
               return search(num, low, mid-1, target);
         
            return search(num, mid+1, high, target);
        }
       
       
        if (target >= num[mid] && target <= num[high])
            return search(num, mid+1, high, target);
       
        return search(num, low, mid-1, target);
    }
}



Here.,

1) Find middle point mid = (low + high)/2
2) If key is present at middle point, return mid.
3) Else If num[low..mid] is sorted
     a) If key to be searched lies in range from num[low] to num[mid], recursion for num[low..mid].
     b) Else recursion for num[mid+1..high]
4) Else (num[mid+1..high] must be sorted)
     a) If key to be searched lies in range from num[mid+1] to num[high], recursion for num[mid+1..high].
     b) Else recursion for num[low...mid]

Time Complexity: O(log n)

Try it on Leetcode