For software engineers, preparing for a tech interview means a lot of practice! Not only must you practice several problems, but you also need to ensure that you cover a wide variety of topics.
In this article, we’re going to tackle a problem on search, which will, in turn, help you crack a number of complex problems — searching an element in a sorted and rotated array.
We solve it using “single-pass binary search by comparing mid and target elements.” This is approach 4 of 4. To check out the other approaches, follow the links:
You have been given a sorted and rotated array "arr" of "N" distinct integers. You are also given an integer "target." Your task is to print the index of the integer "target" in array "arr." If "target" does not exist in "arr," then you need to print -1.
Note:
"arr" contains distinct elements. This means that there is NO pair of indices (i, j) such that 0 <= i < j < N and arr[i] equals arr[j].
"arr" is a rotated sorted array.
The following array adheres to all the above conditions:
Now, if we rotate it three times towards the right, we get a sorted and rotated array:
Let’s take a couple of input examples:
Input 1: arr = [9, 11, 1, 3, 5 ,7] and target = 5 Output 1: 4 Explanation 1: 5 is present at index 4, so we need to print 4.
Input 2: arr = [9, 11, 1, 3, 5 ,7] and target = 8 Output 2: -1 Explanation 2: 8 is not present in "arr," so we need to print -1.
Now that we have a clear understanding of our problem, we will move to the solution.
Approach 4: Single-pass Binary Search by Comparing Mid and Target Elements
The graph of the input array looks something like the below graph:
In the following image, we have simplified the graph. We’ve modified the two curved poly-lines to straight lines by joining the first and last points. Also, we’ve colored the points on the left poly-line green and the points on the other poly-line red.
Key observation: Suppose our search space is bounded by [left, right], and mid is the middle element of the search space. Initially, we will start with a search space that will span the whole array. Then, in each iteration, we reduce the size of the search space in half. We can decide which half to discard by checking if both arr[mid] and target lie on the same part in the image above.
How to discard the range/move pointers:
There are two cases to consider here — one where both mid and target are on the same part, and the second where they’re on different parts. How will we check this? We will compare arr[mid] with arr[0] and do the same for the target. If both target and arr[mid] are greater/lesser than arr[0], then it shows that they lie on the same part, else they lie on different parts.
Case 1: Both mid and target lie on the same part.
In the image above, we can see that mid and target lie on the same part. So, we can search the range marked in red.
Case 2: When mid and target lie on different parts.
We’ll use a trick here — we’ll extend the line of the left part to infinity and the line of the right part to -infinity.
In the above case, to move left and right, we need to compare arr[mid] with the target. However, as they are on different sides, we use a comparator in place of arr[mid], as we just need a value with which we can move our left and right pointers.
So, we will compare the target with arr[0]. Here, targets lie below arr[0], i.e., arr[0] > target. We will set comparator = -INFINITE. Why? Because we need to go to the right side and to do that, we must compare target with a value smaller than the target. (The same logic is used in standard binary search.)
Now, we compare target and comparator. As target > comparator, we move towards the right and set left = left + 1.
Else, if comparator > target, we would move towards the left set right = mid - 1.
Now, let's consider a scenario where the target lies on the left and mid lies on the right side.
In this case, we need to set the comparator to INFINITE. Why? Because our target element lies on the left side, and to move left, we need to compare the target with a value greater than the target.
Algorithm
1. Declare three variables "left", "right," and "mid" for binary search, and initialize left = 0, right = size of array - 1.
2. Run a loop until left <= right:
a. Calculate "mid" as mid = (left + right) / 2.
b. If (arr[0] > arr[mid]) == (arr[0] > target), then this shows arr[mid] and target lie on the same side with respect to target. so set "comparator" = arr[mid].
c. Else:
i. If target < arr[0], then set "comparator" to -INFINITY
ii. Else, set "comparator" to INFINITY
d. If comparator == target, then return mid as we found our target element.
e. If target < comparator, then search target in [left, mid) and move "right" pointer as right = mid - 1.
f. Else, search target in (mid, right] and move left pointer as "left" = mid + 1.
3. Return -1 as we are not able to find the target in our array arr.
Code in C++
Following is the implementation of the above approach in C++.
#include<bits/stdc++.h> using namespace std;
// Function to search target in array 'arr' int searchInRotatedSortedArray(int arr[], int n, int target) { int left = 0, right = n - 1;
while (left <= right) { int mid = (left + right) / 2; int comparator;
// Check if arr[mid] and target lies on same side if ((arr[0] > arr[mid]) == (arr[0] > target)) { comparator = arr[mid]; } else { // Target lies on the right part if (target < arr[0]) { comparator = INT_MIN; }
// Target lies on the left part else { comparator = INT_MAX; } }
// We have found our target if (comparator == target) { return mid; }
// Target lies on [left, mid) if (comparator > target) { right = mid - 1; }
// Target lies on (mid, right] else { left = mid + 1; } }
// We are not able to find a target so return -1. return -1; }
int main() { int n = 10;
int arr[n] = {10, 13, 16, 20, 25, 1, 3, 4, 5, 8};
int target = 4;
cout << searchInRotatedSortedArray(arr, n, target);
return 0; }
Time Complexity
O(log(N)), where "N" is the total number of elements in the given array.
Similar to Approach 3, we are reducing our search space by half at each step. We get recurrence as T(N) = T(N / 2) + C, where C is Constant.
Best Case: O(1) Happens when the comparator equals the target for the first value of mid.
Worst Case: O(log(N)) Happens when the target is not present in the array.
Average case: O(log(N)) Happens when the target is present in the array. We need to do log(N) steps on average to find the target.
Space Complexity
Best Case = Worst Case = Average Case = O(1)
We are using a few extra variables that take O(1) space. Hence, the space complexity will be O(1).
FAQs on Searching an Element in a Sorted and Rotated Array
Question 1: Which is the best approach for searching an element in a sorted and rotated array?
Answer: For searching an element in a sorted and rotated array, using single-pass binary search is better than using linear search or two-pass binary search. There are two ways of doing this: Single-pass Binary Search Using Casework and Single-pass Binary Search by Comparing Mid and Target Elements (which we covered in this post).
Question 2: Would the same solution work if the array had duplicates?
Answer: If we had equal numbers, we might not always be able to decide whether we need to move towards the left or right in our binary search algorithm. So, the same solution will not work in that case.
As pioneers in the field of technical interview prep, we have trained over 5200 software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
.png)
