java二分查找具体步骤是怎样的？手把手教写代码

二分查找的基本原理

二分查找（Binary Search）是一种高效的查找算法，其核心思想是在有序数组中通过 repeatedly dividing the search interval in half 来确定目标值的位置，相较于线性查找的O(n)时间复杂度，二分查找的时间复杂度可优化至O(log n)，尤其适用于大规模数据集的查找场景。

算法的基本步骤如下：

1. 初始化指针：设置两个指针，left指向数组的起始位置（0），right指向数组的末尾位置（length-1）。
2. 中间值计算：计算中间索引 mid = left + (right - left) / 2（避免整数溢出）。
3. 比较中间值：
   • 若 array[mid] == target，则返回 mid，查找成功。
   • 若 array[mid] < target，说明目标值在右半部分，更新 left = mid + 1。
   • 若 array[mid] > target，说明目标值在左半部分，更新 right = mid - 1。
4. 终止条件：当 left > right 时，说明数组中不存在目标值，返回-1。

Java实现二分查找的核心代码

以下是二分查找的标准Java实现（升序数组）：

public class BinarySearch {
    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; // 未找到
    }
}

关键点解析：

• 循环条件：left <= right 确保在搜索区间内查找，避免遗漏元素。
• 中间值计算：left + (right - left) / 2 等价于 (left + right) / 2，但前者可避免 left + right 超过 Integer.MAX_VALUE 的问题。
• 指针更新：left = mid + 1 和 right = mid - 1 确保每次循环都能缩小搜索范围，避免死循环。

二分查找的变体与扩展

查找第一个等于目标值的位置（左边界）

当数组中有重复元素时，若需找到第一个等于 target 的索引，需在找到目标值后继续向左搜索：

public int findFirstOccurrence(int[] array, int target) {
    int left = 0, right = array.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            result = mid;
            right = mid - 1; // 继续向左查找
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

查找最后一个等于目标值的位置（右边界）

类似地，若需找到最后一个等于 target 的索引，找到目标值后需向右搜索：

public int findLastOccurrence(int[] array, int target) {
    int left = 0, right = array.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (array[mid] == target) {
            result = mid;
            left = mid + 1; // 继续向右查找
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

查找第一个大于等于目标值的位置（ lower_bound ）

该变体常用于解决“插入位置”问题，如在有序数组中找到 target 应插入的位置：

public int lowerBound(int[] array, int target) {
    int left = 0, right = array.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left; // 返回第一个大于等于target的索引
}

二分查找的常见错误与注意事项

数组必须有序

二分查找的前提是数组有序（升序或降序），若数组无序，需先排序（排序时间复杂度为O(n log n)），此时二分查找的优势可能被抵消。

避免整数溢出

在计算 mid 时，若直接使用 (left + right) / 2，当 left 和 right 都接近 Integer.MAX_VALUE 时，会导致溢出，推荐使用 left + (right - left) / 2。

循环条件与指针更新

• 循环条件：若使用 left < right，需注意循环结束后 left 和 right 的关系，可能导致遗漏结果。
• 指针更新：必须包含 +1 或 -1，否则可能陷入死循环（当 left == right 时，若不更新，mid 将始终等于 left）。

处理重复元素

标准二分查找在重复元素中返回任意匹配索引的即可，若需返回第一个或最后一个匹配索引，需额外处理（如变体1和2）。

二分查找的实际应用场景

1. 查找与插入：在有序数组中查找元素，或确定元素的插入位置（如 Arrays.binarySearch() 方法）。
2. 数学问题：如求平方根、完全平方数等，可通过二分逼近法快速求解。
3. 算法优化：在动态规划、贪心算法中，常用于优化状态转移或决策过程。
4. 数据库索引：数据库的B+树索引本质上是一种多路二分查找，可快速定位数据。

复杂度分析与性能对比

• 时间复杂度：O(log n)，每次循环将搜索范围缩小一半，效率远高于线性查找的O(n)。
• 空间复杂度：O(1)，仅需常数级额外空间（指针变量），属于原地查找算法。
• 性能对比：对于包含100万个元素的数组，二分查找最多需20次比较（2^20 ≈ 100万），而线性查找最坏需100万次比较。

二分查找是一种基础且高效的查找算法，掌握其原理、实现及变体对解决实际问题至关重要，在使用时需注意数组有序性、边界条件处理及指针更新逻辑，避免常见错误，通过灵活应用二分查找及其变体，可显著提升代码的执行效率,尤其在处理大规模数据时优势明显。