Home » Algorithms

Randomized Binary Search: Algorithm, Time Complexity, Implementations

Randomized Binary Search Algorithm: In this tutorial, we will learn about the Randomized Binary Search, it's time complexity in detail and then, implemented in both C & C++. As a follow up there are several use cases or variations of binary search. By Radib Kar Last updated : August 14, 2023

Earlier we saw how we can implement binary search iteratively and recursively. We found that in normal binary search every time we picked the middle element as pivot.

Randomized Binary Search

In a randomized binary search, instead of picking the middle element, we pick a random element within the range as our pivot. That's the only difference and the rest of the things are the same.

Algorithm for a randomized binary search

So, below is the algorithm for a randomized binary search:

Function

Function 
randomized_binary_search(array, key, left, right)

Where, 
array= input range which is sorted
Key: searching element
left= left index of the range(starting range)
right= right index of the range( ending range)

Steps

1)  Pivot= random index in between [left, right] 
    which can be found like below:
    pivot=left+ rand()%(right-left+1)
2)  If array[pivot]==key
        Key is found. Return
    Else If array[pivot]<key
        Search only in the right half, 
        thus set left= pivot +1, new range [pivot+1, right] 
    Else if array[pivot]>key
        Search only in the left half, 
        thus set right= pivot -1, new range [left, pivot-1]
3)  If left>right
        Break and element is not found

Time Complexity Analysis

Now the question is what will be the time complexity of a randomized binary search? Is it the same as a binary search? That means do it has logarithmic time complexity? Let's check the below mathematical derivation to understand its time complexity:

Let, T(n) be the time complexity of the randomized binary search algorithm

Now, T(n) is the sum of all possible size range generated after we select the pivot. Since we are generating pivot randomly, it can be anything from 1 to n. Each pivot has an equal possibility of being generated which is 1/n.

Thus,

(time taken to generate the pivot randomly)
T(n)= 1/n*T(1)+1/n*T(2)+...+1/n*T(n) +1 
Or, T(n)=( T(1) + T(2) + ..... + T(n) ) / n + 1
Or, nT(n)= ( T(1) + T(2) + ..... + T(n) )+n (multiplying both sides by n) ...eq1

Now putting n=n-1 in the eq1,
(n-1)*T(n-1) = T(1) + T(2) + ..... + T(n-1) + n-1    ...eq2

Now subtracting eq1 and eq2,
n*T(n) - (n-1)*T(n-1) = T(n) + 1
or, (n-1) T(n)=(n-1)T(n-1)+1
or, T(n)=T(n-1) + 1/(n-1)  ...eq4

now, 
T(n-1)=T(n-2)+1/(n-2)
T(n-2)= T(n-3)+1/(n-3)
...
T(2)=T(1)+1/1
T(1)=0 //base case

So,
Replacing all these, we get
T(n)= 1/(n-1)+1/(n-2)+1/(n-3)+...+1/2+1
=Log(n)

So, randomized binary search has also logarithmic time complexity.

Randomized Binary Search (Iterative) Pseudo Code

int random_binary_search_iterative(vector arr, int key){    
    srand(time(NULL));
    int left=0,right=arr.size();
    
    while(left<=right){        
        int mid=left+rand()%(right-left+1);
        if(arr[mid]==key)
        return mid;
        else if(arr[mid]<key)
        left=mid+1;
        else
        right=mid-1;        
    }
    return -1;
}

Randomized Binary Search (Recursive) Pseudo Code

int random_binary_search_recursive(vector<int> arr, int key, int left, int right){
    if(left>right)
    return -1;
    srand(time(NULL));
    
    int mid=left+rand()%(right-left+1);
    if(arr[mid]==key)
        return mid;
    else if(arr[mid]<key)
        return random_binary_search_recursive(arr,key,mid+1,right);
    //else
    return random_binary_search_recursive(arr,key,left,mid-1);          
}

C++ Program to Implement Randomized Binary Search

#include <bits/stdc++.h>
using namespace std;

int random_binary_search_iterative(vector<int> arr, int key)
{
    srand(time(NULL));
    int left = 0, right = arr.size();

    while (left <= right) {
        int mid = left + rand() % (right - left + 1);
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int random_binary_search_recursive(vector<int> arr, int key, int left, int right)
{
    if (left > right)
        return -1;
    srand(time(NULL));

    int mid = left + rand() % (right - left + 1);
    if (arr[mid] == key)
        return mid;
    else if (arr[mid] < key)
        return random_binary_search_recursive(arr, key, mid + 1, right);
    //else
    return random_binary_search_recursive(arr, key, left, mid - 1);
}

int main()
{
    vector<int> arr(1000);

    for (int i = 0; i < 1000; i++)
        arr[i] = i + 1;

    //iterative randomized binary search
    int key = 651;
 
    clock_t tStart1 = clock();
    int index = random_binary_search_iterative(arr, key);
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;
 
    clock_t tend1 = clock();
 
    printf("Time taken in iterative randomized binary search: %.6fs\n", (double)(tend1 - tStart1) / CLOCKS_PER_SEC);
 
    //recursive randomized binary search
    key = 651;
 
    clock_t tStart2 = clock();
    index = random_binary_search_recursive(arr, key, 0, arr.size());
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;
 
    clock_t tend2 = clock();
 
    printf("Time taken in recursive randomized binary search: %.6fs\n", (double)(tend2 - tStart2) / CLOCKS_PER_SEC);

    key = 1003;
 
    index = random_binary_search_iterative(arr, key);
    if (index == -1)
        cout << key << " not found\n";
    else
        cout << key << " found at index(0 based): " << index << endl;

    return 0;
}

Output:

651 found at index(0 based): 650
Time taken in iterative randomized binary search: 0.000066s
651 found at index(0 based): 650
Time taken in recursive randomized binary search: 0.000096s
1003 not found

Though it's found that the recursive implementation has less time taken but that's because of better pivot generated(As it's random). Iterative implementation should have less time taken as there is no function call involved.