二分查找（下）：二分查找的4个变形问题（3，4）

• 查找第一个 大于等于给定值 的元素
• 查找最后一个 小于等于给定值 的元素

一、查找第一个 大于等于给定值 的元素

思路，取中间结点与给定值比较，若大于给定值，则要判断该值是否是第一个大于等于给定值的数据，所以要判断此时的中间结点下标是否是 0，若是则一定是第一个大于等于给定值的元素。若不是 0，则判断中间结点的前一个结点 mid - 1 是否小于给定值，若小于，则表示mid 一定是第一个大于等于给定值的数据。若都不满足则继续二分。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

二、查找最后一个小于等于给定值的元素

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

思路与第一个问题一致。

解答开篇：如何快速定位出一个 IP 地址的归属地？

image