fastest search algorithm to search sorted array

Question

I have an array which only has values 0 and 1. They are stored separately in the array. For example, the array may have first 40% as 0 and remaining 60% as 1. I want to find out the split point between 0 and 1. One algorithm I have in mind is binary search. Since performance is important for me, not sure if binary search could give me the best performance. The split point is randomly distributed. The array is given in the format of 0s and 1s splitted.

Answer 1

The seemingly clever answer of keeping the counts doesn't hold when you are given the array.

Counting is O(n), and so is linear search. Thus, counting is not optimal!

Binary search is your friend, and can get things done in O(lg n) time, which as you may know is way better.

Of course, if you have to process the array anyways (reading from a file, user input etc.), make use of that time to just count the number of 1s and 0s and be done with it (you don't even have to store any of it, just keep the counts).

To drive the point home, if you are writing a library, which has a function called getFirstOneIndex(sortZeroesOnesArr: Array[Integer]): Integer that takes a sorted array of ones and zeroes and returns the position of the first 1, do not count, binary search.