剑指offer-数字在排序数组中出现的次数

题目描述

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

思路

因为是排序数组,因此可以考虑使用二分法.

通过二分法求出指定数字的上下界.通过做差,就是出现的次数.

code

public int GetNumberOfK(int [] array , int k) {
    int lower = binSearchLower(array,k,0,array.length);
    System.out.println(lower);
    int upper = binSearchUpper(array,k,0,array.length);
    System.out.println(upper);
    return upper - lower;
}

// 二分查找,若存在,则返回第一个出现的位置,若不存在,则返回-1
// 通过binSearchLower查找
// 然后再判断这个pos位置的值是否等于key.
public int binSearch(int[] array,int key,int l,int r) {
    int pos = binSearchLower(array,key,l,r);
    if(array[pos] == key) {
        return pos;
    } else {
        return -1;
    }
}

// 二分查找 x >= key 的下界
// ==> 查找第一个大于等于key的位置
// 如果key存在,那么返回值就是key第一次出现的位置,如果不存在,那么就是第一个大于key的元素的位置
public int binSearchLower(int[] array,int key,int l,int r) {
    while(l < r) {
        int mid = l+(r-l)/2;
        if(array[mid] < key ){
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

// 二分查找 x > key 的下界
// ==> 查找第一个大于key的位置
// 如果key存在,那么返回值就是key最后出现的下一位置,如果不存在,那么就是第一个大于key的元素的位置
public int binSearchUpper(int[] array,int key,int l,int r) {
    while(l < r) {
        int mid = l+(r-l)/2;
        if(array[mid] <= key ){
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}