Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Searching an Element in a Sorted and Rotated Array: Linear Search

Last updated by Swaminathan Iyer on Sep 25, 2024 at 11:01 PM | Reading time: 4 minutes

The fast well prepared banner

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Searching an Element in a Sorted and Rotated Array: Linear Search
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings

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:

  • Problem statement
  • Approach explanation
  • Algorithm for the approach
  • Code for the approach
  • Time complexity of the approach
  • Space complexity of the approach

Problem Statement

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 1: Using Linear Search to Find an Element in a Sorted and Rotated Array

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.

Algorithm

  1. Run a loop from index = 0 to arr.length and do:

                       If arr[index] == target then return index.

  1. After the termination of the loop, return -1 as the target was not found.

Code for Implementing Linear Search

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;
}

Time Complexity

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.

Space Complexity

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).

There’s More ...

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

Nervous About Your Next Coding Interview?

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!

Sign up now!

————

Article contributed by Pankaj Sharma

Last updated on: 
October 10, 2024
Author

Swaminathan Iyer

Product @ Interview Kickstart | Ex Media.net | Business Management - XLRI Jamshedpur. Loves building things and burning pizzas!

Attend our Free Webinar on How to Nail Your Next Technical Interview

Register for our webinar

How to Nail your next Technical Interview

1
Enter details
2
Select webinar slot
First Name Required*
Last Name Required*
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

Searching an Element in a Sorted and Rotated Array: Linear Search

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar
entroll-image