Randomized Binary Search Algorithm | Java 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
public class RandomizedBinarySearch { public static int getRandom ( int x , int y ) { return ( x + ( int ) ( Math . random ( ) % ( y - x + 1 ) ) ) ; } public static int randomizedBinarySearch ( int arr [ ] , int low , int high , int key ) { if ( high >= low ) { int mid = getRandom ( low , high ) ; if ( arr [ mid ] == key ) return mid ; if ( arr [ mid ] > key ) return randomizedBinarySearch ( arr , low , mid - 1 , key ) ; return randomizedBinarySearch ( arr , mid + 1 , high , key ) ; } return - 1 ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 4 , 10 , 40 } ; int n = arr . length ; int key = 10 ; int result = randomizedBinarySearch ( arr , 0 , n - 1 , key ) ; System . out . println ( ( result == - 1 ) ? " Element ▁ is ▁ not ▁ present ▁ in ▁ array " : " Element ▁ is ▁ present ▁ at ▁ index ▁ " + result ) ; } }