当前位置：首页 > article >正文

java二分查找算法详解

article 2025/2/28 15:43:35

二分查找遵循分治策略，在升序排列的有序数组中查找元素。核心是反复减半搜索区间，先确定中间元素并与目标元素比较，若相等则查找成功返回其索引；若中间元素大于目标元素，就把搜索区间缩小到左半部分（更新右边界）；若小于，则缩小到右半部分（更新左边界）。如此重复，直至找到目标元素或确定其不存在（左边界大于右边界时）。

例如数组 [1, 3, 5, 7, 9, 11, 13, 15]，找7时中间元素就是7（索引3），能直接找到；找6时，因中间元素7大于6，就将搜索区间缩小至 [1, 3, 5] 继续重复操作，直至确定6不在数组中。

java 代码实现

public class Main {
    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[] arr = {1,2,3,4,5,6,7,8,9};
        int target = 9;
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("目标元素未找到");
        } else {
            System.out.println("目标元素在索引 " + result + " 处");
        }
    }
}

在上述代码中， left 和 right 分别表示当前搜索区间的左右边界，通过循环不断调整这两个边界，直到找到目标元素或者 left 大于 right 。

*在计算中间索引 mid 时，使用 left + (right - left) / 2 而不是 (left + right) / 2 是为了防止在 left 和 right 很大时出现整数溢出的情况。

时间复杂度

二分查找的时间复杂度为O(log n)，其中 n 是数组的长度，这是因为每次迭代都将搜索区间减半。在最坏的情况下，直到搜索区间缩小到只剩下一个元素才确定目标元素是否存在，需要进行log_2 n次比较。

二分查找的变体

在某些情况下，我们不仅要找到目标元素，还希望找到它在数组中第一次出现的位置。例如，在数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 9] 中查找 9，我们希望返回索引 8 而不是 9。

需要将代码改成：

 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) {
                if (mid == 0 || arr[mid - 1]!= target) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

当找到目标元素后，我们还需要检查它是否是第一个出现的，如果当前索引为 0 或者前一个元素不等于目标元素，那么就找到了第一个等于目标值的元素，否则继续在左半部分查找。

有时我们需要找到目标元素在数组中最后一次出现的位置，例如，在数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 9] 中查找 9，我们希望返回索引 9。

public static int findLastEqual(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) {
            if (mid == arr.length - 1 || arr[mid + 1]!= target) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

同理，当找到目标元素后，检查它是否是最后一个出现的，如果当前索引为数组末尾或者后一个元素不等于目标元素，那么就找到了最后一个等于目标值的元素。

查找最后一个满足小于等于目标值条件的元素：

public static int findLastLessEqual(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) {
            if (mid == arr.length - 1 || arr[mid + 1] > target) {
                return mid;
            } else {
                left = mid + 1;
            }
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

当找到一个小于等于目标值的元素后，检查它是否是最后一个满足条件的，如果当前索引为数组末尾或者后一个元素大于目标值，那么就找到了最后一个小于等于目标值的元素，否则继续右分查找更大的满足条件的元素。

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

在实现二分查找时，最常见的错误之一就是边界条件的处理不当。例如，在循环条件中使用 left < right 而不是 left <= right 可能会导致遗漏对最后一个元素的检查。
在计算中间索引 mid 时，如果简单地使用 (left + right) / 2 ，当 left 和 right 都很大时，可能会发生整数溢出。正确的做法是使用 left + (right - left) / 2 来避免这个问题。
二分查找的前提是数组必须是有序的，在使用二分查找之前要确保数组已经按照正确的顺序排序。