Finding Element in Rotated Sorted Array in Python

Using binary search, we can find an element in the given sorted array or list in O(log(n)) time complexity, where n is the number of the numbers in the list. Now let us rotate this sorted array or list at any pivot. However, we don't know the pivot and cannot use it in the operations. For example, if the array = [1, 2, 3, 4, 5, 6, 7] is rotated at pivot 3, then the new array will be array_rotated = [4, 5, 6, 7, 1, 2, 3].

The problem statement for this tutorial is to find a particular number in the rotated sorted array. That too in O(log(n)) time complexity.

Sample Inputs and Outputs:

Input: array = [4, 6, 8, 10, 12, 14, 0, 2]; target = 6

Output: Present at index 1

Input: array = [8, 10, 12, 14, 0, 2, 4, 6]; target = 23

Output: Not found in the array

Input: array = [20, 30, 40, 0, 10]; target = 40

Output: Present at index 2

Assumption:- We will assume that the array contains the unique element, i.e., none of the elements of the array is repeated.

Naïve Approach

In this method, we will first try to find the rotation pivot. Then divide the original array into two sub-arrays. We will perform a binary search in these so sorted sub-arrays. The logic behind finding the pivot element is that it is the only element that, when we move from left to right in the array, will be smaller than its last element. Using this logic, we will find a pivot. The two sub-arrays will be individual sorted arrays. We can hence apply binary search on these two sub-arrays and find the element.

Algorithm

Input array = [4, 5, 6, 7, 1, 2, 3]

The element we need to search = 2

1) Find the pivot of the array. Divide the array into two sub-arrays. (pivot = 3) (Index of element 7).

2) Now, call the binary search function and pass the two sub-arrays to the function.

(a) If the element we need to search is greater than the 0th element of the array, then apply this logic:

(b) Else, we will search for the right sub-array

(Since 2 is less than the 0th element, i.e.,4, so will search for the element in the right sub-array)

3) If we can find the element in the selected sub-array, then we will return the index of the element. Else we will return -1.

We will implement this algorithm in Python:

Code

Output:

The pivot of the array is: 3 The index of 2 in the [4, 5, 6, 7, 1, 2, 3] array is: 5 

Complexity Analysis

Time Complexity: The time complexity of this program is O(log n).

We have used binary search first to find the pivot and then to find the element in the sub-array.

Space Complexity: This program takes O(1) extra memory space. We have not used any additional space to store the array.

Better Solution

Approach: Instead of applying binary search two times, we can solve the problem in a single pass of binary search. We will modify the algorithm to get the desired results. We will create a recursive function that will take the lower and higher index pointers, the array, and the target element. The function will return the index of the target element in the rotated sorted array.

1. Find middle point mid = (l + h)/2
2. Return mid if the key is present at the middle point.
3. Else If arr[l..mid] is sorted
   1. If the key to be searched lies in the range from arr[l] to arr[mid], recur for arr[l..mid].
   2. Else recur for arr[mid+1..h]
4. Else (arr[mid+1..h] must be sorted)
   1. If the key to be searched lies in the range from arr[mid+1] to arr[h], recur for arr[mid+1..h].
   2. Else recur for arr[l..mid]

Below is the implementation of the above idea:

Code

Output:

Index: 2 

Complexity Analysis

Time Complexity: The time complexity of this program is O(log n).

We have used a single binary search algorithm; hence the time complexity is O(log n).

Space Complexity: O(1). We have not used any extra memory space.

How to handle duplicates?

If the array contains duplicate elements, searching the index in O(log n) time complexity is impossible. For instance, if we want to search the index of 0 in the array [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1], then we don't know in which sub-array the element will be possible there. Since we cannot decide the sub-array, we have to search the complete array; hence, the time complexity will be O(n).