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

*to*

**1***. Each pivot has an equal possibility of being generated which is*

**n***.*

**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(vectorarr, 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) 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.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.