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

1.本题知识点

   二分查找

2. 题目描述

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

3. 思路

   一搬情况下，排序数组中的查找都可以通过二分查找来解决。

  ① 通过二分查找查找k,分别找到第一次出现的位置和最后一次出现的索引位置。

  ② 通过k出现的第一和最后的位置直接计算出现次数即可，last - first +1。

  ③ 二分值mid的三种情况：

mid > k ,k出现在左子树，只在左子树中查找mid < k ,k出现在右子树，只在右子树中查找mid = k, 判断k是不是一个k或最后一个k 若k的前一个元素还是等于k，则在左子树中继续二分查找同理，k的后一个元素还是等于k，则在右子树中继续二分查找

   Java版本：

package com.algorithm.array; /** * 统计一个数字在排序数组中出现的次数。 * @author wxq * */ public class NumCount { public static void main(String[] args) { int [] arr = {1,3,5,5,5,8,11,14,14,15}; int count = GetNumberOfK(arr, 14); System.out.println(count); } /** * 思路： 首先通过二分查找查找k,分别找到第一次出现的位置和最后一次出现的位置 * 二分返回三种情况：1. mid > k ,k出现在左子树，只在左子树中查找 * 2. mid < k ,k出现在右子树，只在右子树中查找 * 3. mid = k, 判断k是不是一个k或最后一个k * 若k的前一个元素还是等于k，则在左子树中继续二分查找 * 同理，k的后一个元素还是等于k，则在右子树中继续二分查找 * @param array * @param k * @return */ private static int GetNumberOfK(int [] array, int k) { if(array == null && array.length == 0) return -1; int first = getFirstK(array, 0, array.length-1, k); int last = getLastK(array, 0, array.length-1, k); if(first > -1 && last > -1){ return last - first + 1; } return 0; } /** * 查找k第一次出现的位置 * @param arr * @param left * @param right * @param k * @return */ static int getFirstK(int [] arr,int left ,int right,int k){ if(arr == null && arr.length == 0){ return -1; } //终止条件 while(left <= right){ int midIndex = (left + right) >> 1; if(arr[midIndex] > k){ right = midIndex - 1; } else if(arr[midIndex] < k){ left = midIndex + 1; } //如果mid等于k，且前一个元素不等于k，说明k是第一次出现，返回索引 else{ // midIndex > 0 防止 arr[midIndex-1] 数组下标越界 if((midIndex > 0 && arr[midIndex -1] != k) || midIndex == 0){ return midIndex; } else{//如果前一个元素也跟k相等，则在前面子序列中二分查找 right = midIndex - 1; } } } return -1; } /** * 查找k最后一次出现的位置 * @param arr * @param left * @param right * @param k * @return */ static int getLastK(int [] arr,int left ,int right,int k){ if(arr == null && arr.length == 0){ return -1; } //终止条件 while(left <= right){ int midIndex = (left + right) >> 1; if(arr[midIndex] > k){ right = midIndex - 1; } else if(arr[midIndex] < k){ left = midIndex + 1; } //如果mid等于k，且后一个元素不等于k，说明k是最后一次出现，返回索引 else{ // midIndex < arr.length -1 防止 arr[midIndex+1] 数组下标越界 if((midIndex < arr.length -1 && arr[midIndex +1] != k) || midIndex == arr.length -1){ return midIndex; } else{//如果后一个元素也跟k相等，则在后面子序列中二分查找 left = midIndex + 1; } } } return -1; } }