1.
Introduction-
2.
The naive approach-
3.
Algorithm-
4.
Implementation of the naive approach-
5.
The optimized approach-
6.
Algorithm-
7.
Implementation of the optimized approach-
8.
9.
Key takeaways-
Last Updated: Mar 27, 2024

# Searching and Sorting in Rotated Sorted Array | Part-1

Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

## Introduction-

Let's imagine a scenario in which we have a rotated sorted array of distinct elements, i.e., sorted in ascending order then rotated around some pivot. Now, we have to search a given element in this rotated sorted array. Let's take an example-

In the above example, the initial array is sorted in ascending order from 7 to 13. Suppose we rotate it by three positions towards the left. We get a new array sorted from 10 to 13 and 7 to 9. If we had to search any element in the initial array, it is an easy task as we can use binary search, which will take O(logN) time for searching. But that's not the case with the rotated sorted array.

So let’s find out how we can search any element in the rotated sorted array of distinct elements -

Though there could be many approaches to solve this problem, we will be focusing on the two main methods.

• The naive method starts with finding the pivot in the array and dividing it into subarray around this pivot, and performing a binary search on the sub-array containing the key.
• The second version is an optimized version of this approach which uses a modified binary search.

Let’s learn both these methods in detail one after another-

## The naive approach-

The naive approach to solving this problem starts with finding the pivot element by traversing the array to find an element lesser than its previous element. Then we divide the array into two subarrays around the pivot element. Then we apply binary search in one of the sub-array to find the given element.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Algorithm-

1. Take the array and key from user input.
2. Traverse the array to find the pivot element.
3. Divide the array into two subarrays around the pivot.
4. Use binary search on one of the arrays by the following condition-
• Use the binary search in the left subarray. If the element searched is greater than the element at the 0th index,
• Use the binary search in the right subarray otherwise.

5. If we find the element, return it. if an element is not found, return -1.

## The optimized approach-

Another way to solve this problem is a modified version of the basic approach so that rather than doing multiple traversals of the array, we can search the given element in one traversal. in this approach, and we start with picking the middle element then choosing the sorted array among the left and right subarray. Then we compare the key with the extreme values of these subarrays to choose one for making the recursive calls for the above steps, and we keep doing that until either we find the key or return -1.

## Algorithm-

1. Take the array and key from user input.
2. Find the middle element of the array as mid= (left+right)/2.
3. If the middle element is equal to the key, return mid.
4. Check if the left subarray is sorted( one of both sub-arrays is always sorted)-
• Check the extreme values of the left subarray. If the key lies between it, recursively call step 2 for it.
• Otherwise, recursively call step 2 for the right subarray.

5. Otherwise, the right subarray is sorted-
• Check the extreme values of the right subarray. If the key lies between it, recursively call step 2 for it.
• Otherwise, recursively call step 2 for the left subarray.

6. Keep making recursive calls until we either find the key or reach the base case.

## Implementation of the optimized approach-

Input-

Output-

The time complexity of this algorithm is O(logN), as we are using binary search.

The space complexity of this algorithm is O(1), as no extra space is required.

1. How do you rotate a sorted array?

We can rotate a sorted array by shifting all the elements in the cyclic order, i.e., the first element is moved to the rightmost position while shifting towards the left.

2. How do you search for a target value in a rotated sorted array?

To search a target value in a rotated sorted array, we start with finding the pivot element of the array, i.e., the smallest element. Then we run a binary search on the subarray, which could have the target value. This approach can also be modified with the help of recursion. In the modified approach, we will pick the middle element directly and then recursively call the division for the subarray. Here the subarray for the next step is chosen by checking if they are sorted as only one subarray can be sorted if the pivot is not in the middle.

3. How to check if an array is sorted?

We can check if an array is sorted or not by traversing through it, and if we don't encounter a number that is smaller than its previous number, it is sorted.

4. Which is the fastest algorithm for sorting?

Quicksort is generally considered the fastest algorithm, with a time complexity of O(N*logN).

5. Which searching algorithm is best for sorted arrays?

The binary search algorithm is best for sorted arrays.

## Key takeaways-

In this blog, we learned about searching an element in a rotated sorted array of distinct elements-

• We started with the brute force approach, which first finds the pivot element in the array by checking each element if it is smaller than its previous element. Then, we divide the array into two subarrays, check which can contain the asked element, and call binary search for that subarray until we either reach the base case or get the element.
• The second approach is an optimized version of the brute force approach. In this method, we find the middle element of the array, divide it into two subarrays, pick the one subarray, check if it is sorted, then check if it contains the asked element. If yes, make the recursive call with it, or use the other subarray for the recursion.

Recommended Problem - Merge K Sorted Arrays

Visit here to learn more about arrays. And practice similar problems on Coding Ninjas Studio. If you liked this blog, share it with your friends.

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems