Ex_1_2_09.md

title	date	draft	tags	categories
算法4 Java解答 1.2.09	2019-02-22 07:35:22 +0800	false	JAVA	技术 归档

1.2.09

问题：

Instrument（修改） BinarySearch (page 47) to use a Counter to count the total number of keys examined during all searches and then print the total after all searches are complete. Hint : Create a Counter in main() and pass it as an argument to rank().

分析：

  public static int rank(int key, int[] a, _Counter cnt) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      cnt.increment(); // count
      if (key < a[mid]) {
        hi = mid - 1;
      } else if (key > a[mid]) {
        lo = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }

参考：