Given an unsorted array find the numbers in the array that return true for the following function (defined below).
- Function will return true for value x, if all numbers on left side of x are small and all number on the right side of x are greater.
But the question asks us to use randomized binary search (mid element is not decided by (high + low)/2 but by using a random function) to find the solution.
Link to the question : Original Question Source (Round 3 Onsite question)
Example : Input : [ 4, 3, 1, 5, 7, 6, 10] Output : 5,10
Expected Time Complexity : O(n) Expected Space Complexity : O(n)
Any kind of help will be helpful as i am stuck with the question :).