Count of array elements that can be found using Randomized Binary Search on every array element | Python3 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 ; Given array ; Function Call
import sys NEW_LINE def getDefiniteFinds ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE smallestRight = [ 0 ] * ( n + 1 ) NEW_LINE smallestRight [ n ] = sys . maxsize NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT smallestRight [ i ] = min ( smallestRight [ i + 1 ] , arr [ i ] ) NEW_LINE DEDENT mn = - sys . maxsize - 1 NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( mn < arr [ i ] and arr [ i ] < smallestRight [ i + 1 ] ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT mn = max ( arr [ i ] , mn ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 5 , 4 , 9 ] NEW_LINE print ( getDefiniteFinds ( arr ) ) NEW_LINE