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.
6
-
5Why not just keep a count of the number of zeroes and the number of ones, rather than sorting and searching the array?Darth Egregious– Darth Egregious2015-11-12 20:26:19 +00:00Commented Nov 12, 2015 at 20:26
-
2If all you have is an array for storage, binary search is the fastest you can get. Why would you think that is too slow?ergonaut– ergonaut2015-11-12 20:28:31 +00:00Commented Nov 12, 2015 at 20:28
-
1If the position of the split point is distributed randomly (i.e. the probability of getting a 40/60 split is the same as getting a 1/99, 99/1, 50/50 etc. split) then binary search is the fastest way to solve this.Sergey Kalinichenko– Sergey Kalinichenko2015-11-12 20:29:14 +00:00Commented Nov 12, 2015 at 20:29
-
Hey @Fuser97381, what if you are given the array? This approach becomes sub optimal. Please see my answer.Aman– Aman2015-11-12 20:34:38 +00:00Commented Nov 12, 2015 at 20:34
-
1This sounds like a bad implementation to begin with. Why even have such an array? You can easily replace it with 2 integers (zeroCount & oneCount). There's nothing you can use that array for that you can't do with these 2 counters.Amit– Amit2015-11-12 20:44:49 +00:00Commented Nov 12, 2015 at 20:44
|
Show 1 more comment
1 Answer
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.
1 Comment
John Coleman
Unless the array in question is from an external source, whatever code generated the array could have, with no loss of information and with no wasted memory, kept the counts. It sounds like a classic XY problem. Still -- your answer is a good one so I'll upvote it.