Search Element in a Rotated Sorted Array

Problem Statement: There is an integer array nums sorted in ascending order (with distinct values). Given the array nums after the possible clockwise rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums. We need to search a given element in a rotated sorted array.

Example 1:

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

Output: 4

Explanation: Here, the target is 0. We can see that 0 is present in the given rotated sorted array, nums. Thus, we get output as 4, which is the index at which 0 is present in the array.

Example 2:

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

Output: -1 

Explanation: Here, the target is 3. Since 3 is not present in the given rotated sorted array. Thus, we get output as -1.

Solution:

DisclaimerDon’t jump directly to the solution, try it out yourself first.

Solution 1: Using Linear Search

Approach :

We will iterate through the array completely. While iterating, we have to check if we have found the target element in the array. If we find it, we will return its index. If we iterate completely and still do not find an element in the array. This indicates the target is not present and hence we return -1 as mentioned in the question.

Code:

C++ Code

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

int search(vector<int>& nums,int target) {
    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]==target)
            return i;
    }
    return -1;
     
}

int main() {
    vector<int> nums = {4,5,6,7,0,1,2,3};
    int target = 3;
    cout<<"The index in which the target is present is "<<search(nums,target);
    
    return 0;
}

Time Complexity : O(N)

Reason: We have to iterate through the entire array to check if the target is present in the array.

Space Complexity: O(1)

Reason: We have not used any extra data structures, this makes space complexity, even in the worst case as O(1).

Java Code

import java.util.*;
public class Main {
    static int search(int arr[],int target) {
    for(int i=0;i<arr.length;i++)
    {
        if(arr[i]==target)
            return i;
    }
    return -1;
}
    public static void main(String args[]) {
    int arr[] = {4,5,6,7,0,1,2,3};
    int target = 3;
    System.out.println("The index in which the number is present is "+search(arr,target));
    }
}

    
    

Time Complexity : O(N)

Reason: We have to iterate through the entire array to check if the target is present in the array.

Space Complexity: O(1)

Reason: We have not used any extra data structures, this makes space complexity, even in the worst case as O(1).

Solution 2: Using Binary Search

Intuition :

It is mentioned that the array given is sorted but in a rotated manner. So, we can divide a given array into two parts that are sorted. This gives us hints to use binary search. We can visualize a given array to be composed of two sorted arrays.

Approach :

We divide the array into parts. It is done using two pointers, low and high, and dividing the range between them by 2. This gives the midpoint of the range. Check if the target is present in the midpoint, calculated before, of the array. If not present, check if the left half of the array is sorted. This implies that binary search can be applied in the left half of the array provided the target lies between the value range. Else check into the right half of the array. Repeat the above steps until low <= high. If low > high, indicates we have searched array and target is not present hence return -1. Thus, it makes search operations less as we check range first then perform searching in possible ranges which may have target value.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;

int search(vector < int > & nums, int target) {
  int low = 0, high = nums.size() - 1; //<---step 1

  while (low <= high) { //<--- step 2
    int mid = (low + high) >> 1; //<----step 3
    if (nums[mid] == target)
      return mid; // <---step 4

    if (nums[low] <= nums[mid]) { //<---step 5
      if (nums[low] <= target && nums[mid] >= target)
        high = mid - 1; //<---step 6 
      else
        low = mid + 1; //<---step 7
    } else { //<---step 7
      if (nums[mid] <= target && target <= nums[high])
        low = mid + 1;
      else
        high = mid - 1;
    }
  }
  return -1; //<---step 8
}

int main() {
  vector<int> nums = {4,5,6,7,0,1,2,3};
  int target = 3;
  cout << "The index in which the target is present is " << search(nums, target);

  return 0;
}

Output: The index in which the target is present is 7

Time Complexity: O(log(N))

Reason: We are performing a binary search, this turns time complexity to O(log(N)) where N is the size of the array.

Space Complexity: O(1)

Reason: We do not use any extra data structure, this turns space complexity to O(1).

Java Code

import java.util.*;
public class Main {
    static int search(int arr[], int target) {
        int low = 0, high = arr.length - 1; //<---step 1

        while (low <= high) { //<--- step 2
            int mid = (low + high) >> 1; //<----step 3
            if (arr[mid] == target)
                return mid; // <---step 4

            if (arr[low] <= arr[mid]) { //<---step 5
                if (arr[low] <= target && arr[mid] >= target)
                    high = mid - 1; //<---step 6 
                else
                    low = mid + 1; //<---step 7
            } else { //<---step 7
                if (arr[mid] <= target && target <= arr[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1; //<---step 8
    }
    public static void main(String args[]) {
        int arr[] = {4,5,6,7,0,1,2,3};
        int target = 3;
        System.out.println("The index in which the number is present is " + search(arr, target));
    }
}

Output: The index in which the target is present is 7

Time Complexity: O(log(N))

Reason: We are performing a binary search, this turns time complexity to O(log(N)) where N is the size of the array.

Space Complexity: O(1)

Reason: We do not use any extra data structure, this turns space complexity to O(1).

Special thanks to Dewanshi Paul for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article