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

本文首发于我的个人博客：尾尾部落

题目描述

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

解题思路

正常的思路就是二分查找了，我们用递归的方法实现了查找k第一次出现的下标，用循环的方法实现了查找k最后一次出现的下标。
除此之外，还有另一种奇妙的思路，因为data中都是整数，所以我们不用搜索k的两个位置，而是直接搜索k-0.5和k+0.5这两个数应该插入的位置，然后相减即可。

参考代码

法一：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int len = array.length;
        if(len == 0)
            return 0;
        int first = getFirst(array, k, 0, len-1);
        int last = getLast(array, k, 0, len-1);
        if(first != -1 && last != -1){
            return last - first + 1;
        }
        return 0;
    }
    // 递归
    public int getFirst(int [] array, int k, int start, int end){
        if(start > end){
            return -1;
        }
        int mid = (start + end) >> 1;
        if(array[mid] > k){
            return getFirst(array, k, start, mid - 1);
        }else if(array[mid] < k){
            return getFirst(array, k, mid + 1, end);
        }else if(mid - 1 >= 0 && array[mid-1] == k){
            return getFirst(array, k, start, mid - 1);
        }else
            return mid;
    }
    // 循环
    public int getLast(int [] array, int k, int start, int end){
        int len = array.length;
        int mid = (start + end) >> 1;
        while(start <= mid){
            if(array[mid] > k)
                end = mid - 1;
            else if(array[mid] < k)
                start = mid + 1;
            else if( mid + 1 < len && array[mid+1] == k)
                start = mid + 1;
            else
                return mid;
            mid = (start + end) >> 1;
        }
        return -1;
    }
}

法二：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        return biSearch(array, k+0.5) - biSearch(array, k-0.5);
    }
    public int biSearch(int [] array, double k){
        int start  = 0, end = array.length - 1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(array[mid] > k){
                end = mid - 1;
            }else{
                start = mid + 1;
            }
        }
        return start;
    }
}