Search an Element in a Sorted and Rotated Array in JavaScript

Different approaches to solve this problem

Photo by Markus Winkler on Unsplash

Approach 1: Binary Search

1. Use binary search to find the pivot in the array and divide it into two sub-arrays
2. Note: If the pivot is -1 i.e. the array is sorted and not rotated then do a binary search on the entire array.
3. Now do a binary search on those two sub-arrays.

Note 2: In a sorted rotated array (ascending order) the pivot is the only element for which the next element is smaller than it.

Time Complexity: O(log n)

Space Complexity: O(1)

Approach 2: Modified version of the approach 1

1. Find the middle point in the array mid = (left + right)/2
2. If the middle element and target are equal then return mid
3. If arr[l…mid] is sorted:

• If the key to be searched lies in the range from arr[1] to arr[mid], recur for arr[l…mid]
• Else recur for arr[mid+1 … h]

4. Else arr[mid+1 …. h] must be sorted

• If the key to be searched lies in the range from arr[mid+1] to arr[h], recur for arr[mid+1…h]
• Else recur for arr[l…mid]

Time Complexity: O(log n)

Space Complexity: O(1)

Also read,

Fixed Point in a Given Array in Javascript

First and Last Position of an Element in a Sorted Array in JavaScript