Java二分搜索如何编写迭代版本

在Java中，二分搜索（Binary Search）是一种高效的查找算法，适用于有序的数组或列表。它通过反复将搜索范围分成两半来缩小目标元素的位置。二分搜索有两种常见的实现方式：递归和迭代。下面将详细介绍如何使用迭代方法实现二分搜索，并提供相应的Java代码示例。

迭代版二分搜索的步骤

1. 初始化指针：

   • left：指向搜索范围的左边界，初始为0。
   • right：指向搜索范围的右边界，初始为数组长度减1。

2. 循环查找：

   • 当left小于或等于right时，执行循环。
   • 计算中间位置mid。
   • 比较中间元素nums[mid]与目标值target：
     • 如果相等，返回mid（找到目标）。
     • 如果nums[mid] < target，则目标在右半部分，更新left = mid + 1。
     • 如果nums[mid] > target，则目标在左半部分，更新right = mid - 1。

3. 未找到目标：

   • 如果循环结束后仍未找到目标，返回-1表示目标不存在于数组中。

Java代码示例

public class BinarySearchIterative {
    /**
     * 迭代版二分搜索
     *
     * @param nums   已排序的整数数组
     * @param target 要查找的目标值
     * @return 目标值的索引，如果未找到则返回-1
     */
    public static int binarySearch(int[] nums, int target) {
        int left = 0;               // 搜索范围的左边界
        int right = nums.length - 1; // 搜索范围的右边界

        while (left <= right) {
            // 防止(left + right)溢出
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid; // 找到目标，返回索引
            } else if (nums[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, 21};
        int target = 13;

        int result = binarySearch(sortedArray, target);

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

代码说明

1. 方法binarySearch：

   • 接受一个已排序的整数数组nums和一个目标值target。
   • 使用left和right指针来定义当前的搜索范围。
   • 在while循环中，计算中间位置mid，并根据nums[mid]与target的比较结果调整left和right的值。
   • 如果找到目标值，返回其索引；否则，返回-1。

2. 防止溢出：

   • 计算中间位置时，使用left + (right - left) / 2而不是(left + right) / 2，以防止当left和right都很大时发生整数溢出。

3. main方法：

   • 提供一个示例数组和目标值，调用binarySearch方法并输出结果。

复杂度分析

• 时间复杂度：O(log n)

  • 每次比较都将搜索范围缩小一半，因此时间复杂度是对数级别的。

• 空间复杂度：O(1)

  • 只使用了常数级别的额外空间。

注意事项

• 数组必须有序：二分搜索仅适用于已排序的数组或列表。如果数组未排序，需先进行排序（例如使用快速排序、归并排序等），否则结果将不正确。

• 处理重复元素：如果数组中存在多个相同的目标值，二分搜索可能返回其中任意一个的索引。如果需要找到第一个或最后一个出现的位置，需要对算法进行适当修改。

扩展：查找第一个或最后一个出现的位置

如果需要在有序数组中查找目标值的第一个或最后一个出现位置，可以在找到目标值后，继续向左或向右搜索，直到确定边界。以下是查找第一个出现位置的示例：

public static int binarySearchFirst(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid;
            right = mid - 1; // 继续向左查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

类似地，可以编写binarySearchLast方法来查找最后一个出现的位置。

总结

迭代版二分搜索是一种高效且常用的查找算法，适用于在有序数组中快速定位目标值。通过合理地维护搜索范围的边界，并在每一步缩小搜索范围，可以在对数时间内完成查找操作。