【面试题37-数字在排序数组中出现的次数】

剑指offer第三十七题。

题目描述

统计一个数字在排序数组中出现的次数。

解题思路

看到排序数组，第一个想到的是二分查找，我们来看看这里是如何应用二分查找法的。

我的答案

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int low = 0;
        int high = array.length-1;
        //统计次数
        int count = 0;
        //进入二分查找，注意边界
        while(low <= high){
            //先找到中间点
            int mid = low + (high - low) / 2;
            if(array[mid] > k){
                high = mid - 1;
            }else if(array[mid] < k){
                low = mid + 1;
            }else{
                //走到这边，说明找到了第一个相等的数，先将count加一
                count++;
                //开始从index-1往前找有没有相等的
                int index = mid-1;
                while(index >= 0 && array[index--] == k){
                    count++;
                }
                //开始从index+1往后找有没有相等的
                index = mid + 1;
                while(index < array.length && array[index++] == k){
                    count++;
                }
                //提前跳出while循环，结束
                break;
            }
        }
        return count;
    }
}