问题描述:统计一个数字在排序数组中出现的次数。例如排序数组{1,3,4,4,4,4,4,6,7,9},要查找数字4出现的次数,由于4在这个数组中出现了5次,所以输出5。
分析:看到是排序的数组,理所当然的想到用二分查找。然而需要查找的数字可能在数组中出现多次,所以在查找到第一个目标数字后,还需要对目标数字的左右两边进行顺序扫描,直到找到排序数组中第一个目标数字和最后一个目标数字。因为要查找的数字在长度为n的数组中可能出现n次,所以顺序扫描的时间复杂度为O(n)。
继续思考这个问题,在排序数组中,如果存在多个目标数字,那么......
阅读全文