Search an element in rotated sorted array

Posted in /  

Search an element in rotated sorted array
vinaykhatri

Vinay Khatri
Last updated on May 22, 2024

    You are given a sorted array and a key element as input. Find the index of the key element in the array.

    Example 1:

    Input: arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}
    Key =  3
    Output:  Element Found at 8 index

    Example 2:

    Input: arr[] = {30, 40, 50, 10, 20}
    Key = 10
    Output:  Element Found at 3 index

    Approach 1: Binary Search

    In this approach, we will find the mid of the array first. Then we will consider the array as two sub-arrays, divided in the mid, and search for the element in both parts.

    Algorithm

    1. Find the index of the pivot element.
    2. Search the index of the element in a sorted rotated array, using the pivot element
    3. The array is not rotated if the pivot is not found.
    4. Otherwise, check if the pivot element matches the key.
    5. Search in the first part of the array
    6. If not found, search in the other part of the array.
    7. If found, return the element.

    The implementation of the above-discussed approach is:

    CPP

    #include <bits/stdc++.h>
    using namespace std;
    
    // function to implement the
    // binary search
    int binarySearch(int arr[], int low,
    				int high, int key)
    {
    	if (high < low) 
               return -1; 
            int mid = (low + high) / 2; 
            if (key == arr[mid]) 
               return mid; 
            if (key > arr[mid])
    		return binarySearch(arr, (mid + 1), high, key);
    
    	return binarySearch(arr, low, (mid - 1), key);
    }
    
    // function to find
    // the index of the pivot element
    int searchPivotElement(int arr[], int low, int high)
    {
    	// base cases
    	if (high < low)
    		return -1;
    	if (high == low)
    		return low;
    
    	int mid = (low + high) / 2; 
    	if (mid < high && arr[mid] > arr[mid + 1])
    		return mid;
    
    	if (mid > low && arr[mid] < arr[mid - 1]) 
                    return (mid - 1); 
            if (arr[low] >= arr[mid])
    		return searchPivotElement(arr, low, mid - 1);
    
    	return searchPivotElement(arr, mid + 1, high);
    }
    
    // function to search
    // the index of the element
    // in a sorted rotated array,
    // using the pivot element
    int findElement(int arr[], int n, int key)
    {
    	int pivot = searchPivotElement(arr, 0, n - 1);
    
    	// array is not rotated,
    	// if pivot is not found
    	if (pivot == -1)
    		return binarySearch(arr, 0, n - 1, key);
    
    	// otherwise, check if pivot element
    	// matches with the key
    	if (arr[pivot] == key)
    		return pivot;
    
    	// search in the first part of the array
    	// array is divided around the pivot
    	if (arr[0] <= key)
    		return binarySearch(arr, 0, pivot - 1, key);
    
    	// search in the other part of the array.
    	return binarySearch(arr, pivot + 1, n - 1, key);
    }
    
    int main()
    {
    	int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    	int n = sizeof(arr1) / sizeof(arr1[0]);
    	int key = 3;
    
    	cout << "Element found at the index: "
    		<< findElement(arr1, n, key);
    	cout << "\n\n";
    
    	return 0;
    }
    

    Output

    Element found at the index: 8

    JAVA

    class Main {
    
    	// function to search
    	// the index of the element
    	// in a sorted rotated array,
    	// using the pivot element
    	static int findElement(int arr[], int n, int key)
    	{
    		int pivot = searchPivotElement(arr, 0, n - 1);
    
    		// array is not rotated,
    		// if pivot is not found
    		if (pivot == -1)
    			return binarySearch(arr, 0, n - 1, key);
    
    		// otherwise, check if pivot element
    		// matches with the key
    		if (arr[pivot] == key)
    			return pivot;
    		// search in the first part of the array
    		// array is divided around the pivot
    		if (arr[0] <= key)
    			return binarySearch(arr, 0, pivot - 1, key);
    			
    		// search in the other part of the array.
    		return binarySearch(arr, pivot + 1, n - 1, key);
    	}
    
    	// function to find
    	// the index of the pivot element
    	static int searchPivotElement(int arr[], int low, int high)
    	{
    		// base cases
    		if (high < low)
    			return -1;
    		if (high == low)
    			return low;
    
    		int mid = (low + high) / 2;
    		if (mid < high && arr[mid] > arr[mid + 1])
    			return mid;
    		if (mid > low && arr[mid] < arr[mid - 1]) 
                            return (mid - 1); 
                    if (arr[low] >= arr[mid])
    			return searchPivotElement(arr, low, mid - 1);
    		return searchPivotElement(arr, mid + 1, high);
    	}
    
    	// function to implement the
    	// binary search
    	static int binarySearch(int arr[], int low, int high, int key)
    	{
    		if (high < low) 
                            return -1; int mid = (low + high) / 2; 
                    if (key == arr[mid]) 
                            return mid; 
                    if (key > arr[mid])
    			return binarySearch(arr, (mid + 1), high, key);
    		return binarySearch(arr, low, (mid - 1), key);
    	}
    
    	public static void main(String args[])
    	{
    		int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    		int n = arr1.length;
    		int key = 3;
    		System.out.println("Element found at the index: "
    						+ findElement(arr1, n, key));
    		System.out.print("\n");
    	}
    }
    

    Output

    Element found at the index: 8

    Python

    # function to search
    # the index of the element
    # in a sorted rotated array,
    # using the pivot element
    def findElement(arr, n, key):
    
    	pivot = searchPivotElement(arr, 0, n-1);
    
    	# array is not rotated,
    	# if pivot is not found
    	if pivot == -1:
    		return binarySearch(arr, 0, n-1, key);
    
    	# otherwise, check if pivot element
    	# matches with the key
    	if arr[pivot] == key:
    		return pivot
    	
    	# search in the first part of the array
    	# array is divided around the pivot
    	if arr[0] <= key:
    		return binarySearch(arr, 0, pivot-1, key);
    
    	# search in the other part of the array.
    	return binarySearch(arr, pivot + 1, n-1, key);
    
    # function to find
    # the index of the pivot element
    def searchPivotElement(arr, low, high):
    	
    	# base cases
    	if high < low:
    		return -1
    	if high == low:
    		return low
    	
    	# low + (high - low)/2;
    	mid = int((low + high)/2)
    	
    	if mid < high and arr[mid] > arr[mid + 1]:
    		return mid
    	if mid > low and arr[mid] < arr[mid - 1]:
                    return (mid-1) 
            if arr[low] >= arr[mid]:
    		return searchPivotElement(arr, low, mid-1)
    	return searchPivotElement(arr, mid + 1, high)
    
    # function to implement the
    # binary search
    def binarySearch(arr, low, high, key):
    
    	if high < low:
                    return -1 
            # low + (high - low)/2; 
            mid = int((low + high)/2) 
            if key == arr[mid]: 
                    return mid 
            if key > arr[mid]:
    		return binarySearch(arr, (mid + 1), high,key);
    	return binarySearch(arr, low, (mid -1), key);
    
    # Driver program to check above functions 
    # Let us search 3 in below array
    arr1 = [5, 6, 7, 8, 9, 10, 1, 2, 3]
    n = len(arr1)
    key = 3
    print("Element found at the index: ",
    	findElement(arr1, n, key))
    print("\n")
    
    

    Output

    Element found at the index: 8

    C#

    using System;
    
    class main {
    
    	// function to search
    	// the index of the element
    	// in a sorted rotated array,
    	// using the pivot element
    	static int findElement(int[] arr,int n, int key)
    	{
    		int pivot = searchPivotElemen(arr, 0, n - 1);
    
    		// array is not rotated,
    		// if pivot is not found
    		if (pivot == -1)
    			return binarySearch(arr, 0, n - 1, key);
    
    		// otherwise, check if pivot element
    		// matches with the key
    		if (arr[pivot] == key)
    			return pivot;
    
    		// search in the first part of the array
    		// array is divided around the pivot
    		if (arr[0] <= key)
    			return binarySearch(arr, 0, pivot - 1, key);
    
    		// search in the other part of the array.
    		return binarySearch(arr, pivot + 1, n - 1, key);
    	}
    
    	static int searchPivotElemen(int[] arr, int low, int high)
    	{
    		// base cases
    		if (high < low)
    			return -1;
    		if (high == low)
    			return low;
    
    		int mid = (low + high) / 2;
    
    		if (mid < high && arr[mid] > arr[mid + 1])
    			return mid;
    
    		if (mid > low && arr[mid] < arr[mid - 1]) 
                            return (mid - 1); 
                    if (arr[low] >= arr[mid])
    			return searchPivotElemen(arr, low, mid - 1);
    
    		return searchPivotElemen(arr, mid + 1, high);
    	}
    
    	// function to implement the
    	// binary search
    	static int binarySearch(int[] arr, int low,int high, int key)
    	{
    		if (high < low) 
                            return -1; 
                    int mid = (low + high) / 2; 
                    if (key == arr[mid]) 
                            return mid; 
                    if (key > arr[mid])
    			return binarySearch(arr, (mid + 1), high, key);
    
    		return binarySearch(arr, low, (mid - 1), key);
    	}
    
    	public static void Main()
    	{
    		int[] arr1 = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    		int n = arr1.Length;
    		int key = 3;
    		Console.Write("Element found at the index: "
    					+ findElement(arr1, n, key));
    		Console.Write("\n");
    	}
    }
    
    

    Output

    Element found at the index: 8

    PHP

    <?php
    // function to implement the
    // binary search
    function binarySearch($arr, $low,$high, $key)
    {
    	if ($high < $low) 
                    return -1; $mid = floor($low + $high) / 2; 
            if ($key == $arr[$mid]) 
                    return $mid; 
            if ($key > $arr[$mid])
    		return binarySearch($arr, ($mid + 1), $high, $key);
    		
    	else
    		return binarySearch($arr, $low,($mid -1), $key);
    }
    
    function searchPivotElement($arr, $low, $high)
    {
    	
    	// base cases
    	if ($high < $low)
    		return -1;
    	if ($high == $low)
    		return $low;
    	
    	$mid = ($low + $high)/2;
    	if ($mid < $high and $arr[$mid] >$arr[$mid + 1])
    		return $mid;
    		
    	if ($mid > $low and $arr[$mid] < $arr[$mid - 1]) 
                    return ($mid - 1); 
            if ($arr[$low] >= $arr[$mid])
    		return searchPivotElement($arr, $low,$mid - 1);
    		
    	return searchPivotElement($arr, $mid + 1, $high);
    }
    
    // function to search
    // the index of the element
    // in a sorted rotated array,
    // using the pivot element
    function findElement($arr, $n, $key)
    {
    	$pivot = searchPivotElement($arr, 0, $n - 1);
    	
    	// array is not rotated,
    	// if pivot is not found
    	if ($pivot == -1)
    		return binarySearch($arr, 0,
    					$n - 1, $key);
    	
    	// otherwise, check if pivot element
    	// matches with the key
    	if ($arr[$pivot] == $key)
    		return $pivot;
    
    	// search in the first part of the array
    	// array is divided around the pivot	
    	if ($arr[0] <= $key) 
                   return binarySearch($arr, 0, $pivot - 1, $key); 
            // search in the other part of the array. 
            return binarySearch($arr, $pivot + 1, $n - 1, $key); 
    } 
    // Driver Code 
    $arr1 = array(5, 6, 7, 8, 9, 10, 1, 2, 3); 
    $n = count($arr1); 
    $key = 3; 
    echo "Element found at the index: ",
                 findElement($arr1, $n, $key); 
    echo "\n\n"; 
    ?>
    

    Output

    Element found at the index: 8

    Complexity Analysis:

    Time Complexity: O(log n), as BS takes log n time to find a given array in an element. Space Complexity: O(1), as we did not use any extra space.

    Approach 2: Optimized Binary Search

    This approach is the optimized Binary Search. Here, we will be checking if there is a sorted array or not. In the case of sorted array search in a standard way, the index of the key in both the halves. Find in the other subarray by dividing it into 2 parts in case the let is not found in the first subarray. Otherwise, if the subarray arr[l...mid] is not sorted, then arr[mid...h] will be sorted.

    Algorithm

    1. Check if there is a sorted subarray array arr[l...mid].
      1. In the case of sorted array search in a standard way, the index of the key in both the halves.
      2. Find in the other subarray by dividing it into 2 parts in case the let is not found in the first subarray.
    2. If the subarray arr[l...mid] is not sorted, then arr[mid...h] will be sorted.
    3. Return the index of the element.

    The implementation of the above-discussed approach is:

    CPP

    #include <bits/stdc++.h>
    using namespace std;
    
    // function to search
    // the index of the element
    // in a sorted rotated array,
    // using the pivot element
    int findElement(int arr[], int l, int h, int key)
    {
    	if (l > h)
    		return -1;
    
    	int mid = (l + h) / 2;
    	if (arr[mid] == key)
    		return mid;
    
    	//...1) if there is sorted subarray array arr[l...mid]
    	if (arr[l] <= arr[mid]) 
            { 
                    // in case of sorted array 
                    // search in a standard way 
                    // the index of the key 
                    // in both the halves. 
                    if (key >= arr[l] && key <= arr[mid]) 
                           return findElement(arr, l, mid - 1, key); 
                    // find in the other subarray, by dividing it into 2 parts 
                    // in case if the ley in not found in the first subarray 
                    return findElement(arr, mid + 1, h, key); 
             } 
             //...2) if the subarray arr[l...mid] 
             // is not sorted, then 
             // arr[mid...h] will be sorted 
             if (key >= arr[mid] && key <= arr[h])
    		return findElement(arr, mid + 1, h, key);
    
    	return findElement(arr, l, mid - 1, key);
    }
    
    int main()
    {
    	int arr[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    	int n = sizeof(arr) / sizeof(arr[0]);
    	int key = 3;
    	int i = findElement(arr, 0, n - 1, key);
    
    	if (i != -1)
    		cout << "Element found at the index: " << i << "\n\n";
    	else
    		cout << "Element not found" << "\n\n";
    }
    

    Output

    Element found at the index: 8

    JAVA

    class Main {
    	// function to search
    	// the index of the element
    	// in a sorted rotated array,
    	// using the pivot element
    	static int findElement(int arr[], int l, int h, int key)
    	{
    		if (l > h)
    			return -1;
    
    		int mid = (l + h) / 2;
    		if (arr[mid] == key)
    			return mid;
    
    		//...1) if there is sorted subarray array arr[l...mid]
    		if (arr[l] <= arr[mid]) 
                    { 
                            // in case if sorted array 
                            // search in a standard way 
                            // the index of the key 
                            // in both the halves. 
                            if (key >= arr[l] && key <= arr[mid]) 
                                      return findElement(arr, l, mid - 1, key); 
                            // find in the other subarray, by dividing it into 2 parts 
                            // in case if the ley in not found in the first subarray 
                            return findElement(arr, mid + 1, h, key); 
                     } 
                     //...2) if the subarray arr[l...mid] 
                     // is not sorted, then 
                     // arr[mid...h] will be sorted 
                     if (key >= arr[mid] && key <= arr[h])
    			return findElement(arr, mid + 1, h, key);
    
    		return findElement(arr, l, mid - 1, key);
    	}
    
    	public static void main(String args[])
    	{
    		int arr[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    		int n = arr.length;
    		int key = 3;
    		int i = findElement(arr, 0, n - 1, key);
    		if (i != -1)
    			System.out.println("Element found at the index: " + i + "\n");
    		else
    			System.out.println("Element not found" + "\n");
    	}
    }
    

    Output

    Element found at the index: 8

    Python

    # function to search
    # the index of the element
    # in a sorted rotated array,
    # using the pivot element
    def findElement (arr, l, h, key):
    	if l > h:
    		return -1
    	
    	mid = (l + h) // 2
    	if arr[mid] == key:
    		return mid
    
    	#...1) if there is sorted subarray array arr[l...mid]
    	if arr[l] <= arr[mid]:
                    # in case if sorted array 
                    # search in a standard way 
                    # the index of the key 
                    # in the both the halves. 
                    if key >= arr[l] and key <= arr[mid]:
                            return findElement(arr, l, mid-1, key) 
                    # find in the other subarray, by dividing it into 2 parts 
                    # in case if the ley in not found in the first subarray 
                    return findElement(arr, mid + 1, h, key) 
            #...2) if the subarray arr[l...mid] 
            # is not sorted, then 
            # arr[mid...h] will be sorted 
            if key >= arr[mid] and key <= arr[h]:
                    return findElement(arr, mid + 1, h, key)
    	return findElement(arr, l, mid-1, key)
    
    # Driver program
    arr = [5, 6, 7, 8, 9, 10, 1, 2, 3]
    key = 3
    i = findElement(arr, 0, len(arr)-1, key)
    if i != -1:
    	print ("Element found at the index: % d"% i + "\n")
    else:
    	print ("Element not found")
    

    Output

    Element found at the index: 8

    C#

    using System;
    
    class main {
    
    	// function to search
    	// the index of the element
    	// in a sorted rotated array,
    	// using the pivot element
    	static int findElement(int[] arr, int l, int h,
    					int key)
    	{
    		if (l > h)
    			return -1;
    
    		int mid = (l + h) / 2;
    
    		if (arr[mid] == key)
    			return mid;
    
    		//...1) if there is sorted subarray array arr[l...mid]
    		if (arr[l] <= arr[mid]) 
                    { 
                            // in case if sorted array 
                            // search in a standard way 
                            // the index of the key 
                            // in the both the halves. 
                            if (key >= arr[l] && key <= arr[mid]) 
                                         return findElement(arr, l, mid - 1, key); 
                            // find in the other subarray, by dividing it into 2 parts 
                            // in case if the ley in not found in the first subarray 
                            return findElement(arr, mid + 1, h, key); 
                    } 
                    //...2) if the subarray arr[l...mid] 
                    // is not sorted, then 
                    // arr[mid...h] will be sorted 
                    if (key >= arr[mid] && key <= arr[h])
    			return findElement(arr, mid + 1, h, key);
    
    		return findElement(arr, l, mid - 1, key);
    	}
    
    	public static void Main()
    	{
    		int[] arr = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
    		int n = arr.Length;
    		int key = 3;
    		int i = findElement(arr, 0, n - 1, key);
    
    		if (i != -1)
    			Console.WriteLine("Element found at the index: " + i + "\n");
    		else
    			Console.WriteLine("Element not found");
    	}
    }
    

    Output

    Element found at the index: 8

    PHP

    <?php
    // function to search
    // the index of the element
    // in a sorted rotated array,
    // using the pivot element
    function findElement($arr, $l, $h, $key)
    {
        if ($l > $h) return -1;
    
        $mid = ($l + $h) / 2;
        if ($arr[$mid] == $key)
            return $mid;
    
        //...1) if there is sorted subarray array arr[l...mid]\
        if ($arr[$l] <= $arr[$mid]) 
        { 
                // in case if sorted array 
                // search in a standard way 
                // the index of the key 
                // in the both the halves. 
                if ($key >= $arr[$l] && $key <= $arr[$mid]) 
                        return findElement($arr, $l, $mid - 1, $key); 
               // find in the other subarray, by dividing it into 2 parts 
               // in case if the ley in not found in the first subarray 
               return findElement($arr, $mid + 1, $h, $key); 
         } 
         //...2) if the subarray arr[l...mid] 
         // is not sorted, then 
         // arr[mid...h] will be sorted 
         if ($key >= $arr[$mid] && $key <= $arr[$h]) 
                return findElement($arr, $mid + 1, $h, $key); 
         return findElement($arr, $l, $mid-1, $key); 
    } 
    // Driver Code 
    $arr = array(5, 6, 7, 8, 9, 10, 1, 2, 3, 4); 
    $n = sizeof($arr); 
    $key = 3; 
    $i = findElement($arr, 0, $n-1, $key); 
    if ($i != -1) 
          echo "Element found at the index: ", floor($i), " \n\n"; 
    else 
          echo "Element not found"; ?>
    

    Output

    Element found at the index: 8

    Complexity Analysis:

    • Time Complexity: O(log n), as BS takes log n time to find a given array in an element.
    • Space Complexity: O(1), as we did not use any extra space.

    Wrapping Up!

    In this article, we have learned an amazing as well as easy concept. Searching for an element in a rotated sorted array is one of the most important data structure problems and is usually asked in the top interview questions as well. In this article, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think of a solution and then make optimizations in our code for such kinds of problems. We also discussed two well-explained approaches along with some suitable examples to solve this problem.

    Also, we covered in detail how both of the approaches work and what is their significance of them. We discussed their time complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers could refer to this article.  That’s why this article also contains well-explained codes for all the approaches in the most popular languages along with their respective outputs attached to the article for a better understanding of a wide range of our readers.

    We sincerely hope that this article has walked you through some deep and important concepts and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.

    Happy Learning!

    People are also reading:

    Leave a Comment on this Post

    0 Comments