Java 实现二分查找算法

简介

二分查找（Binary Search），也被称为折半查找，是一种在有序数组中查找特定元素的高效算法。与顺序查找（逐个元素比较）相比，二分查找每次都能将搜索区间缩小一半，大大减少了查找所需的时间复杂度。在 Java 中，实现二分查找算法是掌握基本算法和数据结构的重要一步，本文将详细介绍其基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 基础概念
  2. 使用方法
  3. 常见实践
  4. 最佳实践
  5. 小结
  6. 参考资料

基础概念

二分查找算法的核心思想基于分治策略（Divide and Conquer）。它的前提是数组必须是有序的。算法步骤如下：

  1. 定义两个指针，left 指向数组的起始位置，right 指向数组的末尾位置。
  2. 计算中间位置 mid，通常使用公式 mid = left + (right - left) / 2，这样可以避免 (left + right) 可能导致的整数溢出。
  3. 将目标元素 target 与中间位置的元素 arr[mid] 进行比较：
    • 如果 target 等于 arr[mid]，则查找成功，返回 mid。
    • 如果 target 小于 arr[mid]，则将 right 指针移动到 mid - 1，继续在左半部分查找。
    • 如果 target 大于 arr[mid]，则将 left 指针移动到 mid + 1，继续在右半部分查找。
  4. 重复步骤 2 和 3，直到 left 指针超过 right 指针，此时表示目标元素不存在于数组中，返回 -1。

使用方法

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        } else {
            return binarySearch(arr, mid + 1, right, target);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(arr, 0, arr.length - 1, target);
        if (result == -1) {
            System.out.println("目标元素不存在于数组中");
        } else {
            System.out.println("目标元素在数组中的索引为: " + result);
        }
    }
}

迭代实现

public class BinarySearchIterative {
    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) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("目标元素不存在于数组中");
        } else {
            System.out.println("目标元素在数组中的索引为: " + result);
        }
    }
}

常见实践

查找第一个和最后一个出现的位置

有时候我们不仅需要知道目标元素是否存在，还需要知道它第一次和最后一次出现的位置。以下是实现代码：

public class BinarySearchFirstLast {
    public static int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        result[0] = findFirst(nums, target);
        result[1] = findLast(nums, target);
        return result;
    }

    private static int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (mid == 0 || nums[mid - 1]!= target) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    private static int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                if (mid == nums.length - 1 || nums[mid + 1]!= target) {
                    return mid;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        int[] result = searchRange(nums, target);
        System.out.println("目标元素第一次出现的索引: " + result[0]);
        System.out.println("目标元素最后一次出现的索引: " + result[1]);
    }
}

查找插入位置

在有序数组中找到合适的插入位置，使得数组仍然保持有序。

public class BinarySearchInsertPosition {
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        int result = searchInsert(nums, target);
        System.out.println("目标元素的插入位置: " + result);
    }
}

最佳实践

  1. 确保数组有序：二分查找的前提是数组有序，如果数组无序，需要先进行排序。可以使用 Java 内置的排序方法，如 Arrays.sort()。
  2. 处理边界条件：在编写二分查找代码时，要特别注意边界条件，如数组为空、目标元素在数组的开头或结尾等情况。
  3. 避免整数溢出：计算中间位置时，使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2，防止 left + right 导致的整数溢出。
  4. 选择合适的实现方式：递归实现代码简洁，但可能存在栈溢出问题，适用于数据规模较小的情况；迭代实现性能更好，适用于大规模数据。

小结

二分查找算法是一种高效的查找算法，在有序数组中查找元素时能显著提高查找效率。通过递归或迭代的方式实现，并且可以应用于多种实际场景，如查找第一个和最后一个出现的位置、查找插入位置等。在实际应用中，需要注意数组的有序性、边界条件处理、避免整数溢出以及选择合适的实现方式。

参考资料