# 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
```

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