我有一个只有值 0 和 1 的数组。它们分别存储在数组中。例如，数组可能有前 40% 为 0，其余 60% 为 1。我想找出 0 和 1 之间的分割点。我想到的一种算法是二分查找。由于性能对我来说很重要，所以不确定二分查找是否能给我最好的性能。分割点是随机分布的。该数组以 0 和 1 拆分的格式给出。
最佳答案
当您给数组时，保持计数的看似聪明的答案并不成立。
计数是O(n)，线性搜索也是。因此，计数不是最优的!
二分查找是您的 friend ，可以在 O(lg n) 时间内完成工作，您可能知道这是 way better .
当然，如果您无论如何都必须处理数组(从文件读取、用户输入等)，请利用这段时间来计算 1 和 0 的数量 并完成它(您甚至不必存储任何内容，只需保留计数即可)。
要说明这一点，如果您正在编写一个库，它有一个名为 getFirstOneIndex(sortZeroesOnesArr: Array[Integer]): Integer 的函数，它接受一个由 1 和 0 组成的排序数组并返回第一个1的位置，不计，二分查找。
关于algorithm - 搜索排序数组的最快搜索算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33680654/