Search in Rotated Sorted Array

First, To search in Rotated array, You needs to know what is Rotated Array. So lets see What is Rotated Sorted Array.

What is Rotated Array?

Suppose if all elements of the sorted array are moved to its right by one position. then that array is called Rotated Sorted Array

How we are going to search the element in Rotated Sorted Array

There are 2 Steps

1. Find out the pivot in the array
2. Search the target in the first halves which is from start to pivot - 1 or in the second halves which is from pivot + 1 to end

First Step - Find the pivot
Lets see what is pivot?
Basically the pivot is the largest element in the array from where the elements are in ascending order. From start to pivot the elements are in ascending order and from the element which is next to the pivot to the end, the elements are in ascending order.
The element from which the array will be divided into two sorted arrays is called a pivot.

As shown in the figure above the pivot element is 7. From 7 element we can divide array in the two sorted arrays.
Cases for Finding the pivot
How can we find the pivot?
One way is to search for the Pivot element by going through the each element in the array but it would take O(n) time.
The other way is to search for the pivot element by using the Binary Search which takes O(log n) time. Therefore we will also use the Binary Search.
There are 4 conditions like simple Binary Search

• First is If the element at the middle index is greater than the element which next to the middle index. then the element at the middle index is the Pivot element.
• Second is If the element before the middle index is greater than the element at the middle index, then the element before the middle index is the Pivot element.
• Third is If the element at index start is greater than or equal to the element at middle index means elements next to the middle element are smaller than the element at start. Therefore Pivot element is going to found between the index from start and mid because the pivot is the largest element in the array. Hence change the end pointer to the middle-1.
• On the other hand If the element at index start is smaller than the element at the middle index which means the elements from start to middle index are smaller than the elements from middle+1 to end index. Therefore the pivot element is going to found between middle+1 to end index. Hence change the start pointer to middle+1.

In the end, if the pivot element doesn't found then return -1
THAT'S IT... This is how we can found the pivot element.

Code Sample

def findPivot(arr):
    start = 0 # This is the start index pointer
    end = len(arr) - 1 # This is the last index pointer
    while start <= end:
        mid = int((start + end) / 2)
        if mid < end and arr[mid] > arr[mid+1]:  #Case 1
            return mid
        if mid > start and arr[mid] < arr[mid-1]: #Case 2
            return mid-1
        if arr[start] >= arr[mid]: # Case 3
            end = mid - 1
        if arr[start] < arr[mid]: #Case 4
            start = mid + 1
    return -1

Second Step
Now, we have found our pivot element. Lets find out where our target element located.
We have a Pivot element means we can divide the array into two sorted arrays. By Applying Binary search on both sorted arrays we can find out the target. But there are some conditions.

• First condition is If the element at pivot is equal to the target element then simply return the pivot.
• Second condition is If the starting element is smaller than the target element this means that the our target element will found between start and pivot-1 because all the elements after pivot will be smaller than the starting element.
• If the second condition gets False then our target element will be found in between pivot+1 and end because the starting element will be greater than the target element.
• But if we did not find pivot, it means that the array is not rotated sorted array. In this case just do normal Binary Search

** Code Sample

def rotatedBinarySearch(arr, target):
    pivot = findPivot(arr) # we have found the pivot
    if pivot == -1:  #If we did not found the pivot
        return binarySearch(arr, target, 0, len(arr)-1)
    if arr[pivot] == target:   #case 1
        return True
    if arr[0] <= target:      #case 2
        return binarySearch(arr, target, 0, pivot-1)
    return binarySearch(arr, target, pivot+1, len(arr)-1)  #case 3

That's it! Now you know how to search the target in Rotated Binary Array.

The Complete program is on my GitHub.
https://github.com/prkapadnis/Data-Structure-Python/blob/master/Searching/Binary%20Search/RotatedBinarySearch.py

Thank You 😊😊....