Interview question from a friend

Given an unsorted integer array, how many number are not able to find using binary search?

For example, [2, 3, 4, 1, 5], only the number 1 can't be find using binary search, hence count = 1

[4,2,1,3,5] 4 and 4 and 2 are not searchable => binarySearch(arr, n) return a number that is not equal to num

Expected run time is O(n)

Can't think of an algorithm that can achieve O(n) time :(

Thought about building min and max arr, however, woudln't work as the subarray can mess it out again.

Already knew the O(nlogn) approach, it was obvious, just call binary search for each number and check.