Search Element in a rotated sorted array --- Made it easy .

 This article is about how easily an element can be searched in a rotated sorted array with Binary search .

Input

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

Output:

4

Solution :

There are three steps to solve this problem easily. 

Step 1 : Find out the min element.

Step 2: Apply the standard Binary search on left side of minimum element. 

Step 3: Apply the standard Binary search on right side of minimum element .

First let us find out the minimum element in the array which is 0 ( indexed at 4) and apply the classical Binary search to left side array and right side array .  if any one of the function returns the right value then it can returned as the answer . 

                                      

  

Time Complexity :                                    

For the above 3 steps approach , We will apply Binary Search for the step 1 which is O(logn) time complexity where "n" is no of elements in the array. For step 2 and step 3 we will apply standard Binary search algorithm .So , the total time complexity is O(logn) + O(logn) + O(logn) which is equal to O(logn) as we can ignore the constant time from O(3logn).

Space Complexity :

space complexity is going to be a O(1) as we are not using any extra space . 

Code:

Among all 3 steps , first step is difficult and if you understand this step the many problems can be easily solved of this kind. The idea is, array can be split into two arrays as we do in Binary search and the check if the middle element is less than its previous element and next element of course we check the out of boundary case . if it is minimum then we can return as it is the result . If not, check which side of the array is sorted , out min element will always be on the other side which is not sorted . so, we can keep checking element until we find the min element by following the above step. 

class Solution {
    public int search(int[] nums, int target) {

        int min =  getMinIndex(nums);
        int left = BinarySearch(nums,  0,  min - 1,  target);
        int right = BinarySearch(nums,  min,  nums.length - 1,  target);

        return left == -1 && right == -1 ? - 1 : left == -1 ? right : left;
    }

    private int getMinIndex(int[] nums){
        int left = 0;
        int right = nums.length - 1;
        int n = nums.length;

        while(left <= right){
            if(nums[left] <= nums[right]){
                return left;
            }
            int mid = left + (right - left) / 2;
            int next = ( mid + 1 ) % n;
            int prev = (mid - 1 + n) % n;

            if(nums[mid] <= nums[prev] && nums[mid] <= nums[next]){
                return mid;
            } else if(nums[left] <= nums[mid]){
                left = mid + 1;
            } else if(nums[mid] <= nums[right]){
                right = mid - 1;
            }
        }
        return 0;
    }

    private int BinarySearch(int[] nums, int left, int right, int target){
        while(left <= right){
            int mid = (left + right ) / 2;
            if(nums[mid] == target){
                return mid;
            } else if(nums[mid] > target){
                right = mid - 1;
            } else{
                left = mid + 1;
            }

        }
        return -1;
    }

}

Code may look little bit lengthy but trust me if you get this then implementation is very easy . 

so now we know how to find out min element in rotated array . Below all the problems can be solved by using above approach .

https://leetcode.com/problems/search-in-rotated-sorted-array/

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

May 01, 2021 Tags : #searchinarotatedarray #binarysearch #searching #sorting

Subscribe by Email

Follow Updates Articles from This Blog via Email