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

Solution: Search in a Rotated Array

Explore strategies to search elements in a rotated sorted array, starting from brute force to a modified binary search. Learn how to leverage sorted subarrays and handle duplicate values, improving your understanding of efficient searching algorithms and their time complexities.

We'll cover the following...

Solution #1: Brute force

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