Count of array elements that can be found using Randomized Binary Search on every array element | Java program for the above approach ; Function to find minimum count of array elements found by repeatedly applying Randomized Binary Search ; Stores count of array elements ; smallestRight [ i ] : Stores the smallest array element on the right side of i ; Update smallestRight [ 0 ] ; Traverse the array from right to left ; Update smallestRight [ i ] ; Stores the largest element upto i - th index ; Stores the minimum count of elements found by repeatedly applying Randomized Binary Search ; If largest element on left side is less than smallest element on right side ; Update ans ; Update mn ; Driver Code ; Given array ; Function Call
import java . io . * ; import java . util . * ; class GFG { static int getDefiniteFinds ( int [ ] arr ) { int n = arr . length ; int [ ] smallestRight = new int [ n + 1 ] ; smallestRight [ n ] = Integer . MAX_VALUE ; for ( int i = n - 1 ; i >= 0 ; i -- ) { smallestRight [ i ] = Math . min ( smallestRight [ i + 1 ] , arr [ i ] ) ; } int mn = Integer . MIN_VALUE ; int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( mn < arr [ i ] && arr [ i ] < smallestRight [ i + 1 ] ) { ans ++ ; } mn = Math . max ( arr [ i ] , mn ) ; } return ans ; } public static void main ( String [ ] args ) { int [ ] arr = new int [ ] { 5 , 4 , 9 } ; System . out . println ( getDefiniteFinds ( arr ) ) ; } }