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

# Python Program to search a specific element in the sorted array, which is rotated at a pivot
  
# Defining the function to search the element target in the pivoted array. 
# The function will first find the pivot and then perform a binary search
def pivotedSearch(array, n, target):

    # Find the pivot of the array
    pivot = findPivot(array, 0, n - 1);
    print("The pivot of the array is: ", pivot)
    # If there is no pivot in the array, that means the array is not rotated
    if pivot == -1:
        # Apply binary search on the complete array
        return binarySearch(array, 0, n - 1, target);
  
    # If we could find a pivot, then firstly, we will compare the pivot element with the target element
    if array[pivot] == target:
        return pivot
    # Else, compare the 0th element of the original array to the target
    elif array[0] <= target:
        # Search in the left sub-array
        return binarySearch(array, 0, pivot - 1, target)
    else:
        # Search in the right sub-array
        return binarySearch(array, pivot + 1, n - 1, target)
  
  
# Defining a function to find the pivot of the array 
# For an array [4, 5, 6, 7, 1, 2, 3], it will return 3 
# (index of 7) 
def findPivot(array, l, h):
      
    # base cases of the recursive function
    if h < l:
        return -1
    if h == l:
        return l
    
    # [l + (h - l)/2]. This is same as [(l + h)/2]. We use the prior one to avoid overflow condition
    mid = l + ((h - l) // 2)
    
    if mid < h and array[mid] > array[mid + 1]:
        return mid
    if mid > l and array[mid] < array[mid - 1]:
        return (mid - 1)
    if array[l] >= array[mid]:
        return findPivot(array, l, mid - 1)
    return findPivot(array, mid + 1, h)
  
# Defining the function to perform a standard binary search
def binarySearch(array, l, h, target):
  
    if h < l:
        return -1
          
    # l + (h - l)/2   
    mid = l + ((h - l) // 2)
      
    if target == array[mid]:
        return mid
    if target > array[mid]:
        return binarySearch(array, (mid + 1), h, target)
    return binarySearch(array, l, (mid - 1), target)
  
  
# Calling the function and passing the array and target element to it
# We will search 2 in the below array
array = [4, 5, 6, 7, 1, 2, 3]
n = len(array)
target = 2
print(f"The index of {target} in the {array} array is: ", pivotedSearch(array, n, target))

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.

Find middle point mid = (l + h)/2
Return mid if the key is present at the middle point.
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]
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

# Python program to find an element in a rotated sorted array by a single pass of Binary Search
  
# Creating a function that will return the index of the target element in the array
# If the element is not found, it will return -1
def search(array, low, high, target):

    # Giving the base condition
    if low > high:
        return -1
    
    # Finding the middle element 
    mid = (low + high) // 2
    if array[mid] == target:
        return mid
  
    # Checking which part of the array is sorted
    # If this condition is true, then the left part is sorted
    if array[low] <= array[mid]:
  
        # Since this sub-array is sorted then, we can easily find if the element lies in this sub-array or not by comparing the boundaries
        if target >= array[low] and target <= array[mid]:
            return search(array, low, mid - 1, target)
        else:
        # If the element is not present in the left sub-array, then it is in right sub-array
            return search(array, mid + 1, high, target)
  
    # If the left sub-array is not sorted, then the right sub-array must be sorted
    # CHecking if the element lies in the right sorted sub-array
    if target >= array[mid] and target <= array[high]:
        return search(array, mid + 1, high, target)
    return search(array, low, mid - 1, target)
  
# Calling the function and passing the array to it
array = [5, 6, 7, 8, 9, 1, 2, 3, 4]
target = 3
index = search(array, 0, len(array) - 1, target)
if index == -1:
    print ("The element is not in the array")
else:
    print ("The element is found at the index: ", index)

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

Next TopicFirst Occurrence Using Binary Search in Python

← prev next →