我有一个排序数组,但它不一定是连续的,我需要知道>如果它包含任何重复项。
Array : | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 8 |
我知道我们可以在 O(n) 中线性遍历检查它是否包含任何重复项,但我想知道是否可以使用二分搜索。
最佳答案
不,你不能用二分搜索来做到这一点。所有算法至少需要线性时间。
关于使用二分搜索检查排序的非顺序数组是否有重复项?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31321454/