在二分查找中，如果所要查询的元素在数组中有多个元素存在的情况呢？

来源：7-13 二分查找_设计测试用例和隐藏10年的bug

CDWei

2021-02-24

在二分查找中，如果所要查询的元素在数组中有多个元素存在的情况呢？可以给我一点思路吗？面试被问到

写回答

1回答

ccmouse

2021-03-03

直接能想到的方法是查找任意一个元素，然后向左向右扫描，但如果重复元素非常多的话，就很费时。如果数组长度n，重复元素共有k个，那么复杂度是O(lg(n)+k)

比较高效的是做两次二分查找，分别找到重复元素的头和尾，这就要在我的二分查找基础上微调。

//img.mukewang.com/szimg/603ef8570914356317120968.jpg

我们以找右边边界为例子，因为我们都是半开半闭区间，所以我们要查找第一个比k大的元素。只要将最后一条改为：若k>=arr[m]，将区间缩小为[m,b)，继续二分查找。不过要小心这里如果区间长度是1，但恰好arr[a]==k，这样的情况下区间无法再缩小，需要另行处理，也就是直接确定右边界是b。

查找左边界差不多，不过有些不同，同学可以顺着思路继续下去。

Google面试官亲授-Java面试新手尊享课

为面试新手量身定制的Java面试尊享课，解锁“鲤鱼跃龙门”的妙招

2853 学习 · 180 问题

相似问题

回答 1

回答 2

回答 2

回答 2

回答 1