Data Structures and Algorithms in Java – Arrays – Search in Rotated Sorted Array

Problem:

Given an array of integers which is sorted and rotated , find out if the given element is in the array or not.

A rotated array is an array whose elements are shifted towards the beginning from the end.

For example , consider the array:

input = [1,2,3,4,5]

If this array is rotated once , it becomes [5,1,2,3,4]

If it is rotated twice , it becomes [4,5,1,2,3,4]

If it is rotated five times , it becomes the original array [1,2,3,4,5]

Input:

[4,5,6,7,0,1,2] , Find the index of the number 0.

Output:

4

Try out the solution here:

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

Assumptions:

  • All elements are unique
  • The array size is 5000 maximum
  • Individual elements and the target is in the range from -100000 to 100000

Solution:

The brute force solution to search for an element in this array is just to traverse one element by one and see if it matches the element. The time complexity is O(n).

A better solution of time complexity O(log n) exists.

As soon as you see O(log n) , know that you are going to divide the array into two halves and work on one of the halves and continue the same step till the solution is attained.

Advertisements

Hint:

  1. One half of a sorted rotated array will always be sorted. Only the other half may be unsorted due to the rotation
  2. Check if the element is in the range of the sorted half and if so search in that half recursively, ignore the other half.
  3. If it is not in range of the sorted half, ignore searching it and search the other half recursively

So you always search in only one of the halves and hence the time complexity is O(log n).

Algorithm:

STEP1: Find the middle of the given array

STEP2: If the element at the middle matches the target return the middle index

STEP3: If the first half of the array is sorted (compare first element to the last element of the first half) , check if the target is within the range of the first half

STEP 3a: If target is within that range , search the first half recursively

STEP 3b: If target is not within the range , search the second half recursively

STEP4: If the first half is not sorted , then repeat steps 3, 3a and 3b for the second half

STEP5: Return -1 if element is not present after the above search.

Code:

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

Example:

Let’s try it out for the example

input = [4,5,6,7,0,1,2]

Search for the element 0.

Iteration 1:

Middle index is 3

input[3] = 7 , it does not match the target

The first half of the array [4,5,6,7] is sorted ( compare first element and last element – 4 < 7)

But the element 0 is not within the range of the first half (between 4 and 7) , so ignore it and search the second half [0,1,2]

Iteration 2:

Input: [0,1,2]

Middle index (from the start of the original array is 5. ([4,5,6,7,0,1,2]))

input[middle] = 1 , does not match target

The first half of the array [0,1] is sorted (compare first element and last element – 0< 1)

And the element 0 is within the range (between 0 and 1)

So search in the first half [0,1]

Iteration 3:

Input : [0,1]

Middle index of the above array is 4 (from the start of the original array [4,5,6,7,0,1,2])

input[middle] = 0 , which matches the target , so return the index 4.

The above solution assumed that individual elements are unique.

What if there are duplicates?

It will still work except for one tricky case:

If the start element , the middle element and the last element are all the same.

In that case , you add the below code after calculating the middle element :

 if ((nums[low] == nums[middle])
		            && (nums[high] == nums[middle]))
		        {
		            low++;
		            high--;
		              return search(nums,target,low,high);
		        }

All you have to do is increment the start index and decrement the end index and do the search again recursively as shown above.

Here is the updated code:

package app.example;

public class Solution {
	public static void main(String[] arg) {

		int[] input = new int[] { 2, 2, 0, 2, 2, 2, 2, 2, 2, 2 };

		int index = search(input, 0, 0, input.length - 1);
		System.out.println(index);

	}

	public static int search(int[] nums, int target, int low, int high) {

		if (low > high) {

			return -1;
		}

		int middle = (low + high) / 2;

		if (nums[middle] == target) {

			return middle;
		}

		if ((nums[low] == nums[middle]) && (nums[high] == nums[middle])) {
			low++;
			high--;
			return search(nums, target, low, high);
		}
		if (nums[low] <= nums[middle]) {

			if (nums[low] <= target && target <= nums[middle]) {

				return search(nums, target, low, middle);
			}

			return search(nums, target, middle + 1, high);

		} else

		if (nums[middle + 1] <= nums[high]) {

			if (nums[middle] + 1 <= target && target <= nums[high]) {

				return search(nums, target, middle + 1, high);

			}

			return search(nums, target, low, middle);
		}

		return -1;

	}
}

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s