Search in Rotated Sorted Array

Pratik Kapadnis — Fri, 22 Oct 2021 14:34:45 +0000

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

Find out the pivot in the array
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 😊😊....

BINARY SEARCH

Pratik Kapadnis — Thu, 16 Sep 2021 09:50:57 +0000

Binary Search

Binary Search is the most popular search algorithm and it is also efficient.
If all the names in the world are written down together in order and you want to search for a position of a specific name then Binary Search will accomplish this in a maximum 35 iterations.
Binary Search works only on a sorted array. If we want to use binary search on a collection, then first the collection must be in sorted.
The Runtime complexity of a Binary Search is O(log n)

How It Works

Before beginning the Binary Search first we have to find the start and end of the range.
Binary Search begins by comparing the middle element of the range.
If the middle element is the same as the target element (target element meant the element that we want to search in the range), then it returns the index of that element.
If the middle element did not match the target element then it divides the range into the two halves. The first half consist of the first element to the middle element and the second half consist of the element next to the middle element to the last element.
If the middle element did not match the target element then it compares the middle element with the target element.
If the target element is greater than the middle element then we have to search in the second half by changing the start to middle+1
If the target element is smaller than the middle element then we have to search in the first half by changing the end to the middle-1.
Repeat this procedure recursively until start <= end. In any iterations, if we get the target element is equal to the middle element, then we return the index of the middle element. if we did not get the target element in the range then we return the -1.

A little demo on how Binary Search works

Here is a sample of what the binary search code might look like