1. 本题知识点

二分查找

2. 题目描述

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

输入：[1,2,3,3,3,3,4,5],3返回：4

3. 解题思路

用二分查找到重复元素出现的第一个下标，再用二分查找到重复元素出现的最后一个下标，相减获得出现次数。

4. 代码

public class Solution {
       public int GetNumberOfK(int[] array, int k) {
           int firstIndex = GetFirstIndex(array, k);        int lastIndex = GetLastIndex(array, k);        if (firstIndex == -1 || lastIndex == -1) {
               return 0;        }        return lastIndex - firstIndex + 1;    }    public int GetFirstIndex(int[] array, int k) {
           int high = array.length - 1;        int low = 0;        while (low <= high) {
               int mid = (low + high) / 2;            if (k > array[mid]) {
                   // 如果 k > 中间值，则在右半数组查找                low = mid + 1;            } else if (k < array[mid]) {
                   // 如果 k < 中间值，则在左半数组查找                high = mid - 1;            } else {
                   // 如果 k = 中间值，则判断 mid-1 是否等于 k                mid = mid - 1;                if (mid < low || array[mid] != k) {
                       // 不等于 k，则找到第一个下标                    return mid + 1;                } else {
                       // 等于 k,继续二分查找                    high = mid;                }            }        }        return -1;    }    public int GetLastIndex(int[] array, int k) {
           int high = array.length - 1;        int low = 0;        while (low <= high) {
               int mid = (low + high) / 2;            if (k > array[mid]) {
                   low = mid + 1;            } else if (k < array[mid]) {
                   high = mid - 1;            } else {
                   mid = mid + 1;                if (mid > high || array[mid] != k) {
                       return mid - 1;                } else {
                       low = mid;                }            }        }        return -1;    }}