数组在排序数组中出现的次数

数据结构和算法

例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，输出4

最差的二分查找

找到一个3，然后左右顺序扫描，分别找出第一个3和最后一个3，因此要查找的数字在长度为n的数组中可能出现O(n)次，所以顺序扫描的时间复杂度为O(n)，所以速度和顺序扫描整个数组统计出3的次数是一样的。

改进的二分查找

前面时间主要消耗在如何确定重复的第一个K和最后一个k上，其实也可以用二分查找，而不是顺序查找

如何找第一个k，其实如果k在中间，只需判断前面一个是否有k，如果是，再在前半段查找，后半段也是一样。