JZ37 数字在升序数组中出现的次数

描述: 给定一个长度为 n的非降序数组和一个非负数整数k，要求统计k在数组中出现的次数. 示例1

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

思路:用传统的暴力破解很轻松就能做出来,这里考察主要是二分查找, 看到有序的数组进行查找,第一眼想到的就是采用二分来进行查找. 1.这里我在写二分查找的时候,有几个地方需要注意:在写大循环,while(low<=high)的时候符号是<=. 2.在最后通过二分查找找到目标值k之后,定义两个指针向两边进行查找完毕之后,要记得break,结束循环,经常写算法题遇到时间复杂度过高的问题就是在于一些break的使用

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){
          
   
                low=mid+1;
            }else if(array[mid]>k){
          
   
                high=mid-1;
            }else{
          
   
                count++;
                int index1=mid-1;
                int index2=mid+1;
                while(index1>=0 && array[index1]==k){
          
   
                    count++;
                    index1--;
                }
                while(index2<array.length && array[index2]==k){
          
   
                    count++;
                    index2++;
                }
                break;
            }
        }
        return count;
    }
}