学习笔记39——在排序数组中查找数字（二分查找法，时间复杂度O(logn)）

题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4。 思路：假设要统计数字k在排序数组中出现的次数，基于二分查找法直接找到第一个k和最后一个k，在分别找到第一个k和最后一个k的对应下标以后，就能计算出k在排序数组中出现的次数。 核心代码如下：

//寻找排序数组中第一个k，如果数组中不存在k，返回-1 int GetFirstK(int* data, int length, int k, int start, int end){ if(start > end) return -1; int midIndex = (start + end) / 2; int midData = data[midIndex]; if(midData == k){ if((midIndex > 0 && data[midIndex - 1] != k) || midIndex == 0) return midIndex; else end = midIndex - 1; } else if(midIndex > k) end = midIndex - 1; else start = midIndex + 1; return GetFirstK(data, length, k, start, end); } //寻找排序数组中最后一个k，如果数组中不存在k，返回-1 int GetLastK(int* data, int length, int k, int start, int end){ if(start > end) return -1; int midIndex = (start + end) / 2; int midData = data[midIndex]; if(midData == k){ if((midIndex > 0 && data[midIndex + 1] != k) || midIndex == 0) return midIndex; else start = midIndex + 1; } else if(midIndex > k) end = midIndex - 1; else start = midIndex + 1; return GetLastK(data, length, k, start, end); } //计算k在数组中出现的次数 int GetNumberOfK(int* data, int length, int k){ int number = 0; if(data != nullptr && length > 0){ int first = GetFirstK(data, length, k, 0, length); int last = GetLastK(data, length, k, 0, length); if(first > -1 && last > -1) number = last - first + 1; } return number; }