Algorithms for Coding Interviews in C++/

...

/

Solution: Search in a Rotated Array

Solution: Search in a Rotated Array

Let's look at a detailed analysis of all the ways to search in a rotated array.

We'll cover the following...

Solution #1: Brute Force

Press + to interact
#include <iostream>
using namespace std;
int searchRotatedArray(int arr[], int left, int right, int s) {
  if (right <= 0) // Sanity check
    return -1;
  
  for(int i = 0; i <= right; i++)
    if(arr[i] == s)
      return i; // If found return index
  
  return -1; // Return -1 otherwise
}
int main() {
  int arr[] = {40,100,-100,-40,0,24,40};
  cout << searchRotatedArray(arr, 0, 6, 40) << endl;
}

This is just a simple linear search. It iterates over the entire array and checks if the element being searched for is equal to the current element in the array. You might have first come up with this solution, however, it is not the most efficient solution and would not get you very far in an interview. You’d need to mention this without implementing it and then build it up from there.

Time Complexity

The time complexity of this solution is in O(n)O(n) ...

Access this course and 1400+ top-rated courses and projects.