Randomized Binary Search Algorithm | Python3 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
import random NEW_LINE def getRandom ( x , y ) : NEW_LINE INDENT tmp = ( x + random . randint ( 0 , 100000 ) % ( y - x + 1 ) ) NEW_LINE return tmp NEW_LINE DEDENT def randomizedBinarySearch ( arr , l , r , x ) : NEW_LINE INDENT if r >= l : NEW_LINE INDENT mid = getRandom ( l , r ) NEW_LINE if arr [ mid ] == x : NEW_LINE INDENT return mid NEW_LINE DEDENT if arr [ mid ] > x : NEW_LINE INDENT return randomizedBinarySearch ( arr , l , mid - 1 , x ) NEW_LINE DEDENT return randomizedBinarySearch ( arr , mid + 1 , r , x ) NEW_LINE DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 2 , 3 , 4 , 10 , 40 ] NEW_LINE n = len ( arr ) NEW_LINE x = 10 NEW_LINE result = randomizedBinarySearch ( arr , 0 , n - 1 , x ) NEW_LINE if result == - 1 : NEW_LINE INDENT print ( ' Element ▁ is ▁ not ▁ present ▁ in ▁ array ' ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ' Element ▁ is ▁ present ▁ at ▁ index ▁ ' , result ) NEW_LINE DEDENT DEDENT