Search an element in a sorted and rotated Array
- ishitajuneja01
- Mar 30, 2023
- 4 min read
Preparing for a technical interview requires a lot of practice for software developers!
Now that top tech companies have multiple rounds, every candidate must possess extreme skills to get a job in their dream company.
For practicing, each coder must have the best resource to learn from. That said, you’re at the right place! Yes, we’re going to introduce the concept of search in rotated sorted array since it’s a widely asked interview question.
Search is a DSA concept that allows users to access the required information from a data set. When you find results in google search, it simply means that the Search DSA concept is programmed.
In this article, we will mainly look at how you can find an element in a sorted and a rotated array using search. Let’s dive in!
How to search in a rotated sorted array?
Before moving into reading the main deal of the article, let’s understand what a rotated sorted array is. We know that sorted arrays are nothing but a sequence of characters organized in a specific order.
By rotated sorted array we denote the array’s rotation that shifts the elements from a point to a specific position. This rotation can be both clockwise and anti-clockwise.
Here’s an example to understand this concept thoroughly. Let’s say we’re given a sorted array,
Array: [1, 2, 3, 4, 5, 6, 7, 8]
Now when we rotate it, it comes to [6,7,8,1,2,3,4,5]
The key is 4 and you’re asked to search in rotated sorted array the given key and its index. The number 4 appears in the 6th index (the index starts from 0 and in the 6th position of the rotated array, the number 4 appears).
DSA Fact: To find duplicate in array, the search concept is the most used approach. It will help the user to find the duplicate value within an array and help in removing it.
Methods to search in rotated sorted array
To find an element using search in the sorted and rotated array, there are two interesting methods to employ. Let us briefly learn about both of them individually.
Method 1: Find the point where rotation started
Finding the main point (pivot), dividing the given input into sub-arrays, and proceeding with a search are the objectives. The pivot element's following element will be less in a sorted and rotated manner.
We will have search indices in the l and r range with mid. The mid denotes the index at the middle. If rotation occurred in the left side, the item at l will be larger than the item at mid. If rotation occurred in the right half, mid will be larger than r.
From the same example given above, the pivot element is 8 because the next element is 1 and it is smaller than the previous element.
After locating the pivot, the array is separated as subarrays. The divided arrays are now sorted and binary search is employed to search the key element.
Steps:
With the aid of binary search, locate the pivot point.
Fix the pointer that is low to serve as the initial array index and the high pointer to be the final array index.
Calculate the midpoint between tlow and the highest values.
If the number in the mid-1 point is bigger than the value at the middle, that value is returned as the main point.
If The value at mid+1 is smaller, use the mid number as the main point.
Now, select the left half if the number at the lowest point is bigger than the one at mid position. If not, choose the right half instead.
Based on the pivot, split the input array into subs.
Use the binary search function to locate any of the main subarrays.
If the item is bigger than the 0th element, check in array that is at the left.. If not, present check the right side.
If the answer is found there, send the index value. If not, return -1.
Since we’re using binary search and as it needs log n comparisons to find the item, the time complexity would be O(log N) whereas the space would be O(1) since not much space was used.
Method 2: Direct Binary Search (Exclude Pivot Point)
When we find a pivot point a lot of time gets used. To avoid that this binary search method will help. The objective is to find the result with one run of binary search rather than two or more search runs.
The aim is to write a recursive algorithm to perform the binary search in the [l, r] range. For each iterative call:
The midpoint is calculated as mid = (l + h) / 2.
Then it is determined if l to mid is sorted or (mid+1) to h is sorted.
Finally the next search region is found based on that and is repeated until the element is located. If not, l surpasses h.
Steps:
To find the key, use a recursive algorithm to perform binary search.
Calculate the midpoint mid = (l + h)/2
Return mid if the key is present.
If the value at l is smaller than the value at mid, then arr[l... mid] is sorted.
If the key to be searched is in the range arr[l] to arr[mid], repeat for arr[l... mid].
Else, repeat for arr[mid+1... h]
Instead, arr[mid+1. . . h] is sorted:
If the key to be found is in the region from arr[mid+1] to arr[h], repeat for arr[mid+1... h].
Otherwise, repeat for arr[l... mid]
Since we’re using binary search and as it needs log n comparisons to find the item, the time complexity would be O(log N) whereas the space would be O(1) since not much space was used.
Final thoughts
Arrays are one of the well-known data structures that have so many problems related to it.
Additionally, search is a great DSA concept that must be known by all coders since the modern world makes use of it vastly.
We hope our blog serves you the purpose right. If you’re curious to learn more about other coding topics like linked lists, next permutation, find duplicates in arrays and such, check our website.
Comments