1. 引言
二分查找（Binary Search）是一种常见的搜索算法，专门用于在有序数组或列表中查找元素的位置。它通过每次将搜索空间缩小一半，从而极大地提高了查找效率。相比于线性查找算法，二分查找的时间复杂度为 O(log n)，在处理大规模数据时非常高效。
2. 二分查找算法的基本原理
二分查找要求搜索目标的数据集合是有序的。通过将数组从中间位置一分为二，逐步缩小搜索范围，最终找到目标元素或确定目标元素不存在。算法的关键在于，每次比较时，将要查找的元素与中间元素进行比较，并据此决定继续向左半部分或右半部分搜索。
3. 二分查找适用问题类型
二分查找算法适用于以下类型问题：
- 在有序数组中查找元素的索引。
- 寻找有序数组中满足条件的边界值，如第一个大于等于目标值的元素或最后一个小于等于目标值的元素。
- 确定某一条件下的最优解，例如在单调递增或递减函数中查找某一阈值。
4. 二分查找通用实现模板
4.1 标准二分查找模板
首先，我们来看最基础的二分查找算法实现。这个模板适用于在有序数组中查找某个目标值，并返回其索引。
public class BinarySearch {/*** 标准二分查找，查找目标值的索引* @param arr 已排序的数组* @param target 要查找的目标值* @return 目标值的索引，如果不存在则返回 -1*/public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 找到目标值，返回索引} else if (arr[mid] < target) {left = mid + 1; // 在右半部分继续查找} else {right = mid - 1; // 在左半部分继续查找}}return -1; // 没有找到目标值}public static void main(String[] args) {int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};int target = 7;int result = binarySearch(sortedArray, target);if (result != -1) {System.out.println("目标值 " + target + " 在索引 " + result);} else {System.out.println("目标值 " + target + " 不存在于数组中");}}
}
解释：
left和right分别指向数组的左右边界。- 每次通过
mid = left + (right - left) / 2计算中间索引。 - 如果中间值
arr[mid]恰好等于目标值，则返回mid作为目标值的索引。 - 如果中间值小于目标值，表示目标值在右侧，则更新左边界
left = mid + 1。 - 如果中间值大于目标值，表示目标值在左侧，则更新右边界
right = mid - 1。
4.2 二分查找的变体模板
除了标准的二分查找，还有一些变体问题常常需要我们在查找过程中找到特定的边界值。
查找第一个大于等于目标值的元素
public static int findFirstGreaterOrEqual(int[] arr, int target) {int left = 0;int right = arr.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] >= target) {result = mid; // 记录当前 mid 作为可能的结果right = mid - 1; // 继续在左半部分查找} else {left = mid + 1; // 在右半部分查找}}return result;
}
查找最后一个小于等于目标值的元素
public static int findLastLessOrEqual(int[] arr, int target) {int left = 0;int right = arr.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] <= target) {result = mid; // 记录当前 mid 作为可能的结果left = mid + 1; // 继续在右半部分查找} else {right = mid - 1; // 在左半部分查找}}return result;
}
5. 二分查找的时序图
为了更好地理解二分查找的执行过程，我们可以通过时序图展示二分查找的各个步骤。时序图展示了从开始到查找到目标值（或确认目标值不存在）的过程。
时序图
6. 案例分析：电商系统中的二分查找
在电商系统中，二分查找可以被应用在很多场景中，例如：
- 商品价格查询：在大量已排序的商品价格列表中快速找到某一商品价格，或者确定某个商品价格在列表中的位置。
- 库存检查：通过二分查找，可以快速确定某一商品的库存量，或者查找某类商品的库存是否充足。
- 订单历史记录查询：在按时间排序的订单历史记录中，快速查找某一时间段的订单。
案例 1：价格查询
假设电商系统有一份已排序的商品价格列表，用户需要查询某个商品的价格是否存在，或者找到第一个高于某个价格的商品。
public class PriceQuery {public static int findFirstPriceGreaterOrEqual(int[] prices, int targetPrice) {int left = 0;int right = prices.length - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (prices[mid] >= targetPrice) {result = mid;right = mid - 1;} else {left = mid + 1;}}return result;}public static void main(String[] args) {int[] prices = {100, 200, 300, 400, 500, 600, 700};int targetPrice = 350;int index = findFirstPriceGreaterOrEqual(prices, targetPrice);if (index != -1) {System.out.println("第一个大于等于 " + targetPrice + " 的价格是: " + prices[index]);} else {System.out.println("没有找到大于等于 " + targetPrice + " 的商品价格");}}
}
案例 2：订单历史记录查询
在按日期排序的订单记录中，用户希望快速找到某一天的订单记录，或者查找最近的一笔订单。
public class OrderQuery {public static int findClosestOrder(int[] orders, int targetDate) {int left = 0;int right = orders.length - 1;int closest = -1;while (left <= right) {int mid = left + (right - left) / 2;if (orders[mid] == targetDate) {return mid; // 找到精确匹配的订单} else if (orders[mid] < targetDate) {closest = mid; // 记录当前最近的订单left = mid + 1;} else {right = mid - 1;}}return closest; // 返回最近的订单}public static void main(String[] args) {int[] orderDates = {20220101, 20220201, 20220301, 20220401, 20220501};int targetDate = 20220315;int index = findClosestOrder(orderDates, targetDate);if (index != -1) {System.out.println("最近的订单日期是: " + orderDates[index]);} else {System.out.println("没有找到合适的订单");}}
}
7. 二分查找的常见问题
虽然二分查找看似简单，但在实现过程中容易遇到一些问题。
- 越界问题：由于计算中间索引时使用
(left + right) / 2，当left和right很大时，可能会导致整型溢出。为此，推荐使用left + (right - left) / 2计算中间索引。 - 终止条件不清晰：二分查找的循环条件应为
left <= right，而不是left < right，否则可能会漏掉最后一个可能的索引位置。
