Randomized Binary Search Algorithm | C ++ program to implement recursive randomized algorithm . ; To generate random number between x and y ie . . [ x , y ] ; A recursive randomized binary search function . It returns location of x in given array arr [ l . . r ] is present , otherwise - 1 ; Here we have defined middle as random index between l and r ie . . [ l , r ] ; If the element is present at the middle itself ; If element is smaller than mid , then it can only be present in left subarray ; Else the element can only be present in right subarray ; We reach here when element is not present in array ; Driver code
#include <iostream> NEW_LINE #include <ctime> NEW_LINE using namespace std ; int getRandom ( int x , int y ) { srand ( time ( NULL ) ) ; return ( x + rand ( ) % ( y - x + 1 ) ) ; } int randomizedBinarySearch ( int arr [ ] , int l , int r , int x ) { if ( r >= l ) { int mid = getRandom ( l , r ) ; if ( arr [ mid ] == x ) return mid ; if ( arr [ mid ] > x ) return randomizedBinarySearch ( arr , l , mid - 1 , x ) ; return randomizedBinarySearch ( arr , mid + 1 , r , x ) ; } return -1 ; } int main ( void ) { int arr [ ] = { 2 , 3 , 4 , 10 , 40 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int x = 10 ; int result = randomizedBinarySearch ( arr , 0 , n - 1 , x ) ; ( result == -1 ) ? printf ( " Element ▁ is ▁ not ▁ present ▁ in ▁ array " ) : printf ( " Element ▁ is ▁ present ▁ at ▁ index ▁ % d " , result ) ; return 0 ; }