格物致知

据说是微软的一道题。

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

算法的思想，使用修改后的二分查找法，找到最左边 2 的下标为 1 ，最后边 2 的下标为 3，然后返回3 – 1 + 1 = 3 即可，算法复杂度为 logN。

编码的时候，用一个变量 last 来存储本次查找到的位置，然后根据情况变换查找方向，就可以分别确定 left 和 right 下标的值。

代码实现：

package org.leeing.interview;

/**
 * 题目：在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3]
 * 2 的出现次数是3次。
 *
 * @author leeing
 *
 */
public class NumberCounter {
	public static void main(String[] args) {
		int a[] = { 1, 2, 2, 2, 2, 3, 4 };
		int counter = numbercounter(a, 4);
		System.out.println(counter);
	}

	static int numbercounter(int[] a, int num) {
		int left = binarysearch(a, num, true);
		int right = binarysearch(a, num, false);
		System.out.println("left is :" + left);
		System.out.println("right is :" + right);

		if (left != -1 && right != -1) {
			return right - left + 1;
		} else {
			return 0;
		}
	}

	static int binarysearch(int[] a, int target, boolean isLeft) {
		int left = 0, right = a.length - 1;
		int last = 0;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (a[mid] < target) {
				left = mid + 1;
			} else if (a[mid] > target) {
				right = mid - 1;
			} else {
				last = mid;

				if (isLeft) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			}
		}
		return last > 0 ? last : -1;
	}
}