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






Comments and Discussions

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





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.