Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C++

Solution: Search in a Rotated Array

Explore how to efficiently search for an element in a rotated sorted array by comparing brute force and modified binary search methods. Understand dividing the array into sorted subarrays, handling duplicates, and analyzing time complexities, enabling you to tackle this common coding interview problem.

We'll cover the following...

Solution #1: Brute Force

C++
#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) ...