Algorithms for Coding Interviews in Java/

...

/

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
class SearchArray {
 static int searchRotatedArray(int arr[], int left, int right, int n) {
  if (right <= 0) // Sanity check
   return -1;
  for (int i = 0; i < right; i++)
   if (arr[i] == n)
    return i; // If found return index
  return -1; // Return -1 otherwise
 }
 public static void main(String args[]) {
  int arr[] = {40,100,-100,40,0,24,40};
  System.out.println(searchRotatedArray(arr, 0, 6, -100));
 }
}

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 (lines 6-7). You might come up with this solution first. However, it is not the most efficient solution, and it 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.