二分查找及其变种

二分查找

• 原理：针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0
• 时间复杂度为O(logn)
  • 计算方式， 如下图， 最坏的情况下n/2k=1时， 找到元素，求得 k=log2n
• 注意：mid=(low+high)/2可能导致溢出，可以写成low+(high-low)/2， 更进一步可写成low+((high-low)>>1)

publicclassBinarySearch {
    /**
     * 二分查找方法
     *
     * @param arr    已排序的数组
     * @param target 目标值
     * @return目标值在数组中的索引，如果未找到则返回 -1
     */
publicstaticintbinarySearch(int[] arr, inttarget) {
        intleft = 0; // 左边界
intright = arr.length - 1; // 右边界

while(left <= right) {
            intmid = left + (right - left) / 2; // 计算中间位置

if(arr[mid] == target) {
                returnmid; // 找到目标值，返回索引
} elseif(arr[mid] < target) {
                left = mid + 1; // 目标值在右半部分，调整左边界
} else{
                right = mid - 1; // 目标值在左半部分，调整右边界
}
        }

        return-1; // 未找到目标值
}

    publicstaticvoidmain(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15}; // 已排序的数组
inttarget = 7; // 目标值

intresult = binarySearch(arr, target);

        if(result != -1) {
            System.out.println("目标值 " + target + " 在数组中的索引为: " + result);
        } else{
            System.out.println("目标值 " + target + " 未找到");
        }
    }
}

变种

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

publicclassBinarySearchFirstOccurrence {

    /**
     * 查找第一个值等于给定值的元素
     *
     * @param arr    已排序的数组
     * @param target 目标值
     * @return第一个等于目标值的元素的索引，如果未找到则返回 -1
     */
publicstaticintbinarySearchFirstOccurrence(int[] arr, inttarget) {
        intleft = 0; // 左边界
intright = arr.length - 1; // 右边界

while(left <= right) {
            intmid = left + (right - left) / 2; // 计算中间位置

if(arr[mid] < target) {
                left = mid + 1; // 目标值在右半部分，调整左边界
} elseif(arr[mid] > target) {
                right = mid - 1; // 目标值在左半部分，调整右边界
} else{
                // 找到目标值，检查是否是第一个
if(mid == 0 || arr[mid - 1] != target) {
                    returnmid; // 是第一个匹配的元素
} else{
                    right = mid - 1; // 继续向左搜索
}
            }
        }

        return-1; // 未找到目标值
}

    publicstaticvoidmain(String[] args) {
        int[] arr = {1, 3, 5, 5, 5, 7, 9, 11, 13, 15}; // 已排序的数组
inttarget = 5; // 目标值

intresult = binarySearchFirstOccurrence(arr, target);

        if(result != -1) {
            System.out.println("第一个值等于 " + target + " 的元素索引为: " + result);
        } else{
            System.out.println("目标值 " + target + " 未找到");
        }
    }
}

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

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) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

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

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 地址的归属地？

如果 IP 区间与归属地的对应关系不经常更新，我们可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。如何来排序呢？我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。

然后，这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。

当我们要查询某个 IP 归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。