Author
Swaminathan Iyer
Product @ Interview Kickstart | Ex Media.net | Business Management - XLRI Jamshedpur. Loves building things and burning pizzas!
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 help you crack a number of complex problems — searching an element in a sorted and rotated array.
We solve it using “linear search.†This is approach 1 of 4.
To check out the other approaches, follow the links:
Here, we cover:
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:
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.
It is the most straightforward possible approach to solve this problem. Basically, we use brute force here. In this approach, we will linearly scan the array and check whether the target exists or not.
If arr[index] == target then return index.
Here’s the C++ code to implement the algorithm above:
/*
Time Complexity:Â O(N)
Space Complexity: O(1)
Where N is the total number of elements in the given array.
*/
#include<iostream>
using namespace std;
// Function to search target in array ‘arr’
int searchInRotatedSortedArray(int arr[], int n, int target)
{
// Linearly check every element if its equal to target
for (int i = 0; i < n; i++)
{
if (arr[i] == target)
{
return i;
}
}
// We are not able to find target in array so returning -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;
}
O(N), where “N” is the total number of elements in the given array.
â€Best Case: O(1)
When the target is the first element of the array.
Worst Case: O(N)
When the target is not present in the array, we need to check O(N) elements. â€
Average Case: O(N)
On average, we need to check O(N) elements to see if they match the target or not.
Best Case = Worst Case: O(1) = Average Case = O(1)
â€We are using a few extra variables that take O(1) space. Hence, the space complexity will be O(1).
This method works, but the brute-force approach is a bit trivial. Let’s figure out a better way. The given array is sorted. What would we do if the given input was sorted but not rotated? Can we apply binary search? Read this article to find out:
Searching an Element in a Sorted and Rotated Array: Two-pass Binary Search
Let Interview Kickstart help you!
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!
————
Article contributed by Pankaj Sharma
Time Zone:
Get your enrollment process started by registering for a Pre-enrollment Webinar with one of our Founders.
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
The 11 Neural “Power Patterns” For Solving Any FAANG Interview Problem 12.5X Faster Than 99.8% OF Applicants
The 2 “Magic Questions” That Reveal Whether You’re Good Enough To Receive A Lucrative Big Tech Offer
The “Instant Income Multiplier” That 2-3X’s Your Current Tech Salary
Just drop your name and email so we can send your Power Patterns PDF straight to your inbox. No Spam!
By sharing your contact details, you agree to our privacy policy.
Time Zone: Asia/Dhaka
We’ve sent the Power Patterns PDF to your inbox — it should arrive in the next 30 seconds.
📩 Can’t find it? Check your promotions or spam folder — and mark us as safe so you don’t miss future insights.
We’re hosting a private session where FAANG insiders walk through how they actually use these Power Patterns to crack interviews — and what sets top performers apart.
🎯 If you liked the PDF, you’ll love what we’re sharing next.
Time Zone:
