Search Element in Rotated Sorted Array

DevSniper
Published : 25 July 2024

135 Views

Given a rotated sorted array with distinct values of size N and a target value. Your task is to find the target value within the array.

Example 1 :-

arr : [5,7,9,2,3,4], Target : 7

Output : Target index : 1

Example 2 :-

arr : [13,15,3,4,6,7,9] Target : 5

Output : Target is not present in array.

Example 3 :-

arr : [2,5,6,7,8,9], Target : 6

Output : Target index : 2

Constraints :

1 <= arr.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of arr are distinct/unique.
-10^4 <= target <= 10^4

Brute force (Naive) Approach

The brute force approach involves iterating through the array and checking each element to see if it matches the target value or not.

C++

Java

Python

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

int SearchTargetIndex(int arr[], int n, int target)
{
    for(int i=0; i<n; i++) {
        if(arr[i]==target) {
            return i;
        }
    }
    return -1;
}
int main()
{
    int arr[] = {4,5,6,7,8,1,2,3};
    int target =7;
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = SearchTargetIndex(arr,n,target);
    if(index<0) {
        cout<<"Target is not present in array."<<endl;
    } else {
        cout<<"Target index : "<<index<<endl;
    }
}

Target index : 3

Time Complexity : O(N)

Space Complexity : O(1)

Using Binary Search

Binary search is a highly effective method for finding elements in a sorted array. In our case of a rotated sorted array. Here direct binary search is not feasible due to rotation but we can modify binary search here to find the target value efficiently.

Idea of modified Binary Search : When dividing array into to halves (calculating mid), at least one half of the array remains sorted at any given point, so by determining which half is sorted. We can efficiently decide where to continue our search using binary search.

Steps :

Take left (0) and right(N-1) point and iterate until left is less than equal to right. (similar as Binary Search)
Calculate mid point of left and right point.
Compare the target element with the mid point if matches this will be our answer.
Identify is left half sorted or right half sorted.
if left half sorted
- if element present in sorted subarray then set right = mid -1
- otherwise set left = mid +1
if right half sorted
- if element present in sorted then set left = mid+1
- otherwise right = mid -1

C++

Java

Python

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

int SearchTargetIndex(int arr[], int n, int target)
{
    int left=0,right = n-1;
    while(left<=right) {
        int mid=(left+right)/2;
        if(arr[mid]==target) {
            return mid;
        }
        // left half is sorted
        if(arr[left]<=arr[mid]) {
            if(target>=arr[left] &amp;&amp; target<arr[mid]) {
                right=mid-1;
            } else {
                left=mid+1;
            }
        } else {
            // right half is sorted
            if(target>arr[mid] &amp;&amp; target <=arr[right]) {
                left=mid+1;
            } else {
                right=mid-1;
            }
        }
    }
    return -1;
}
int main()
{
    int arr[] = {5,6,7,8,1,2,3,4};
    int target =7;
    int n = sizeof(arr) / sizeof(arr[0]);
    int index = SearchTargetIndex(arr,n,target);
    if(index<0) {
        cout<<"Target is not present in array."<<endl;
    } else {
        cout<<"Target index : "<<index<<endl;
    }
}

Target index : 2

Time Complexity : O(logN)

Space Complexity : O(1)