数据结构与算法基础篇--二分查找

必要前提：有序数组

算法简述：通过不断取中间值和目标target值进行比较（中间值：mid = (left + right) / 2）

• 如果目标值等于中间位置的值，则找到目标，返回中间位置
• 如果目标值小于中间位置的值，则在左半部分继续查找：更新右边界为 right = mid - 1
• 如果目标值大于中间位置的值，则在右半部分继续查找：更新左边界为 left = mid + 1

二分查找的时间复杂度： O(log n)，其中 n 是要查找的元素个数（通常是一个有序数组的长度）。

java代码实现

    // 二分查找方法public static int binarySearch(int[] array, int target) {int left = 0;int right = array.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (array[mid] == target) {return mid; // 找到目标值，返回索引} else if (array[mid] < target) {left = mid + 1; // 目标值在右半部分} else {right = mid - 1; // 目标值在左半部分}}return -1; // 没有找到目标值}

这里解释一下为什么中间值用这种int mid = left + (right - left) / 2写法，

而不是这种int mid = (right + left) / 2;

1，避免溢出风险

在 Java 中，int类型的最大值是 2^31 - 1，如果 left 和 right 非常大，直接计算 mid = (left + right) / 2; 可能会导致溢出。

2，清晰明了

使用 left + (right - left) / 2 明确地展示了计算 mid 的逻辑，使得代码更加清晰易懂。直观地表达了将 left 和 right 之间的中点作为 mid 的计算方法。

github中二分法图像化展示

二分法html，欢迎各位直接拉到本地展示使用

力扣中关于二分法的题目编号

• 简单难度：

        704，35，278，374，69

• 中等难度：

        33，34，240，162，300

• 困难难度：

        4，154，287，875，668