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
function getRandom ( x , y ) { return Math . floor ( x + Math . floor ( Math . random ( ) * 10 ) % ( y - x + 1 ) ) ; } function randomizedBinarySearch ( arr , l , r , x ) { while ( l <= r ) { let m = getRandom ( l , r ) ; if ( arr [ m ] == x ) return m ; if ( arr [ m ] < x ) l = m + 1 ; else r = m - 1 ; } return - 1 ; } let arr = [ 2 , 3 , 4 , 10 , 40 ] ; let n = arr . length ; let x = 10 ; let result = randomizedBinarySearch ( arr , 0 , n - 1 , x ) ; if ( result == - 1 ) document . write ( " " ) ; else document . write ( " " , result ) ;