Number of times a number appears in an ascending array

Knowledge point Array   Two points

describe

         Given a length of n And a nonnegative integer k , Ask for statistics k The number of occurrences in the array

Data range ：0 < n < 1000 , 0 < k < 100, The value of each element in the array satisfies  0 < val < 100
requirement ： Spatial complexity  O(1), Time complexity  O(logn)

         Obviously , The given array is non descending , That is, the array is in ascending order , It's just that there are elements of the same size . This problem is to use binary search to locate the element first k Position in the array , Then look for elements of the same size as yourself in the left and right directions respectively from this position and count the number . Because arrays are ordered , So stop searching in this direction as long as you find an element that is not as big as yourself in each direction .

        The main investigation is whether you can write binary search , And some fine nodes when writing binary search , For example, recursive call , Sub array head and tail critical value processing , And how recursive calls exit . Here is the code , Write a separate article to sort out the details .

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array == null || array.length == 0) {
            return 0;
        }
       // Let's look in two k Where it appears in the array , Then traverse left and right from this position k Number of occurrences 
        int length = array.length;
        int index = binarySearch(array, k, 0, length);
        if (-1 == index) {
            return 0;
        }
        int i = index - 1;
        int j = index + 1;
        int count = 1;
        boolean findLeft = true;
        boolean findRight= true;
        while(findLeft || findRight) {
            if (findLeft) {
                if (i >= 0 && k == array[i]) {
                    count++;
                    i--;
                } else {
                    findLeft = false;
                }
            }
            if (findRight) {
                if (j < length && k == array[j]) {
                    count++;
                    j++;
                } else {
                    findRight = false;
                }
            }
        }
        return count;
    }
    
    // Binary search algorithm 
    public int binarySearch(int [] array, int k, int start, int end) {
        if (start == end) {
            return -1;
        }
        int mid = (start + end) / 2;
        if (k == array[mid]) {
            return mid;
        } else if (k < array[mid]) {
            end = mid;
        } else {
            start = mid + 1;
        }
        int index = binarySearch(array, k, start, end);
        return index;
    }
}