Search in Rotated Sorted Array

You are given an integer array, sorted in ascending order and a target integer. Suppose that the array is rotated at some pivot point that is unknown to you. For example, the array {0, 1, 2, 4, 5, 6, 7} after 3 rotations becomes {4, 5, 6, 7, 0, 1, 2}. You need to search for the target element in the array and find out the index of that element. If the element is not present in the array, return -1.

It is guaranteed that the array is rotated at some pivot point. Solve the problem in O(log (N) ) time with no extra space.

Sample Input - Arr = {4, 5, 6, 7, 0, 1, 2}, Target = 0.
Expected Output - 4.

Sample Input - Arr = {4, 5, 6, 7, 0, 1, 2}, Target = 3.
Expected Output = -1.

Algorithm

One method to solve the problem is linear search algorithm. The time complexity for this approach would be linear O (N).

A more efficient approach to solve the problem would be to apply binary search algorithm. This method would take O (Log (N)) time complexity.

  1. Initialize left = 0 and right = N-1, where N is the length of the array.
  2. While (left <= right), do the following
    Calculate the middle position using the left and right positions. If the element in the middle position is equal to the target value, return the middle index.

    If the value at the middle index greater than or equal to the element at left index, we check for two conditions –
    If target element if greater than or equal to the element at left index and less than the element at middle index, we set right pointer to (middle – 1), else we set left pointer to (middle + 1).

    If the value at middle index is less than the value at left index, this means that the array is rotated at this part. In this case, we check for two conditions –
    If the target element is greater than the element at middle index and less than or equal to the element at right index, we set left = (middle + 1), else we set right = ( middle – 1 ).

For a better understanding, check out the code below.

#include <bits/stdc++.h>
using namespace std;

int search(vector<int>& nums, int target) {
    if(nums.size()==0){
        return -1;
    }
    int left=0;
    int right = nums.size()-1;
    while(left<=right){
        int mid = (left+right)/2;
        if(nums[mid]==target){
            return mid;
        }
        if(nums[mid]>=nums[left]){
            if(target>=nums[left] && target<nums[mid]){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }else{
            if(target>nums[mid] && target<=nums[right]){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
    }
    return -1;
}

int main(){
	vector<int> arr = {4, 5, 6, 7, 0, 1, 2};
	int target = 2;
	cout<<search(arr, target);
	return 0;
}

Also, check out another popular interview problem Sorted Array to BST.

One comment

Leave a Reply

Your email address will not be published.