Randomized Binary Search Algorithm | To generate random number between x and y ie . . [ x , y ] ; A iterative randomized binary search function . It returns location of x in given array arr [ l . . r ] if present , otherwise - 1 ; Here we have defined middle as random index between l and r ie . . [ l , r ] ; Check if x is present at mid ; If x greater , ignore left half ; If x is smaller , ignore right half ; if we reach here , then element was not present ; Driver code
from random import randint NEW_LINE def getRandom ( x , y ) : NEW_LINE INDENT return randint ( x , y ) NEW_LINE DEDENT def randomizedBinarySearch ( arr , l , r , x ) : NEW_LINE INDENT while ( l <= r ) : NEW_LINE INDENT m = getRandom ( l , r ) NEW_LINE if ( arr [ m ] == x ) : NEW_LINE INDENT return m NEW_LINE DEDENT if ( arr [ m ] < x ) : NEW_LINE INDENT l = m + 1 NEW_LINE DEDENT else : NEW_LINE INDENT r = m - 1 NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT 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