# Randomized Binary Search

In the above article, we are going to see a variation of binary search which is known as a randomized binary search where we find the pivot element randomly instead of taking the middle element.
Submitted by Radib Kar, on July 20, 2020

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. In the case of 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.

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

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

## Algorithm

```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 implementation)

```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 implementation)

```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++ implementation:

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

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.