在排序数组中查找数字

题目：

​ 统计一个数字在排序数组中出现的次数。例如输入排序数组{1， 2， 3， 3， 3， 3， 4， 5}和数字3，由于3在这个数组中出现了4次，因此输出4。

分析：

1. 第一种解法：蛮力法，顺序遍历数组，统计出数字3出现的次数，不过这就没有利用到题目中给的有序，时间复杂度为 O(n)，还会有更快的方法。
2. 第二种解法：利用二分查找的思想（时间复杂度 O(logn)）来解决问题。首先先找到数组中3出现的第一个位置first，然后再找到数组中3最后一次出现的位置 last，last-first + 1就是数字3出现的次数。

代码：

解法二实现

class NumberCountSolution {

    private int getFirstK(int[] data, int length, int k, int start, int end) {
        if (start > end) {
            return -1;
        }

        int midIndex = (start + end) / 2;
        int midData = data[midIndex];

        if (midData == k) {
            if (midIndex > 0 && data[midIndex - 1] != k || midIndex == 0) {
                return midIndex;
            } else {
                end = midIndex - 1;
            }
        } else if (midData > k) {
            end = midIndex - 1;
        } else {
            start = midIndex + 1;
        }
        return getFirstK(data, length, k, start, end);
    }

    private int getLastK(int[] data, int length, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int midIndex = (start + end) / 2;
        int midData = data[midIndex];
        if (midData == k) {
            if (midIndex < length - 1 && data[midIndex + 1] != k || midIndex == length - 1) {
                return midIndex;
            } else {
                start = midIndex + 1;
            }
        } else if (midData < k) {
            start = midIndex + 1;
        } else {
            end = midIndex - 1;
        }
        return getLastK(data, length, k, start, end);
    }

    public int getNumberCount(int[] data, int length, int k) {
        int number = 0;
        if (null == data || length < 0) {
            return number;
        }

        int first = getFirstK(data, length, k, 0, length - 1);
        int last = getLastK(data, length, k, 0, length - 1);

        if (first > -1 && last > -1) {
            number = last - first + 1;
        }
        return number;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 3, 3, 3, 4, 5};
        NumberCountSolution solution = new NumberCountSolution();
        int numberCount = solution.getNumberCount(data, data.length, 3);
        System.out.println(numberCount);
    }
}

还有一种牛客网上的实现方法

//因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5
//这两个数应该插入的位置，然后相减即可。
class NowCoderSolution {
    
    public static int getCount(int[] data, int k) {
        return binSearch(data, k + 0.5) - binSearch(data, k - 0.5);
    }

    private static int binSearch(int[] data, double num) {
        int start = 0;
        int end = data.length - 1;
        while (start < end) {
            int mid = (end - start) / 2 + start;
            if (data[mid] < num) {
                start = mid + 1;
            } else if (data[mid] > num) {
                end = mid - 1;
            }
        }
        return start;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 3, 3, 3, 4, 5};
        int numberCount = getCount(data, 3);
        System.out.println(numberCount);
    }
}

[编程题]数字在排序数组中出现的次数