我有一个只有值0和1的数组.它们分别存储在数组中.例如,数组可能有40%为0,剩余60%为1.我想找出0和1之间的分裂点.我想到的一种算法是二进制搜索.由于性能对我来说很重要,不确定二进制搜索是否能给我带来最佳性能.分裂点是随机分布的.该数组以0s和1s格式分割.
当你获得阵列时,保持计数的看似聪明的答案并不成立 .
计数是O(n),线性搜索也是如此.因此,计数不是最佳的!
二进制搜索是你的朋友,可以及时完成任务,O(lg n)你可能知道的更好.
当然,如果你有反正处理阵列(从文件,用户输入等阅读),利用这一时间仅计算的数量1s,并0s与它做(你甚至不必存储任何它,只是保持计数).
要驱动点回家,如果你正在编写一个库,它有一个被调用的函数getFirstOneIndex(sortZeroesOnesArr: Array[Integer]): Integer,它采用1和0的排序数组并返回第一个的位置1,不计算二进制搜索.
