二分查找法

BinarySearch.java

public class BinarySearch {
  /**
   * 查找排序数组中值等于 key 的 index
   * @param key    目标值
   * @param a      排序数组
   * @return       值等于 key 时的 index，若找不到则为 -1
   */
  public static int rank(int key, int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;  // Java 中 3/2 = 1, Java 是向 0 取整
      if (key < a[mid]) hi = mid - 1; // 在左侧
      if (key > a[mid]) lo = mid + 1;
      else              return mid;
    }
    return -1;
  }
}

BinarySearchRecursion.java

public class BinarySearchRecursion {
  /**
   * 查找排序数组中值等于 key 的 index
   * @param key    目标值
   * @param a      排序数组
   * @return       值等于 key 时的 index，若找不到则为 -1
   */
  public static int rank(int key, int[] a) {
    return rankHelper(key, a, 0, a.length - 1);
  }
  
  
  private static int rankHelper(int key,int[] a, int lo, int hi) {
    // 方法返回的含义是 值等于 key 的 index，因此递归函数直接return
    // 递归本身是在调整 lo, hi 的值,即 a 的区间
    if(lo>hi) return -1;
    int mid = lo + (hi - lo) / 2;  // Java 中 3/2 = 1
    if      (key < a[mid]) return rank(key, a, lo, mid - 1); // 在左侧
    else if (key > a[mid]) return rank(key, a, mid + 1, hi);
    else                   return mid;
  }
}