题目：

在排序数组中，找出给定数字的出现次数.比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。

输入：

1,2,2,2,3

输出：

1(1)
2(3)
3(1)

package tengxun;

/*
 * 题目：
 * 在排序数组中，找出给定数字的出现次数.比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
 * 输入：1,2,2,2,3
 * 输出：
 * 1(1)
 * 2(3)
 * 3(1)
 * 解题思路：
 * 二分查找算法直接找到第一个k及最后一个k
 * 最坏情况下时间复杂度为O(logn) */
import java.util.Scanner;

public class Solution {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String str[] = in.next().split(",");// 键盘输入一行空格/逗号分隔的整数数组
        int[] nums = new int[str.length];// 键盘输入一行空格/逗号分隔的整数数组
        for (int i = 0; i <= str.length - 1; i++) {
            nums[i] = Integer.valueOf(str[i]);
        }
        for (int i = 0; i <= str.length - 1; i++) {
            if (i == 0 || i != 0 && nums[i] != nums[i - 1]) {
                System.out.println(nums[i]+ "(" + (getEndK(nums, nums[i])
                                        - getStartK(nums, nums[i]) + 1) + ")");
            }
        }
    }

    private static int getEndK(int[] array, int k) {// 获取元素k最后出现位置
        // TODO Auto-generated method stub
        int low = 0, high = array.length - 1;
        while (low < high) {
            int mid = (low + high + 1) / 2;
            if (array[mid] <= k)
                // 当要查找的值比中位数大于等于时，把查找的低位限制为mid
                low = mid;
            else
                // 当要找的值比 中位数小时，把查找的高位限制为mid-1
                high = mid - 1;
        }
        return low;
    }

    private static int getStartK(int[] array, int k) {// 获取元素k第一次出现位置
        // TODO Auto-generated method stub
        int low = 0, high = array.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            // 当要找的值比 中位数小于等于时，把查找的高位限制为mid+1
            if (array[mid] >= k)
                high = mid;
            else
                // 当要找的值比 中位数大时，，把查找的低位限制为mid+1
                low = mid + 1;
        }
        return low;
    }
}