Java Binary Search 如何实现高效查找

在Java中，二分查找（Binary Search）是一种高效的查找算法，适用于已排序的数据集合。它通过反复将查找范围减半来快速定位目标元素。以下是二分查找的实现步骤和示例代码：

实现步骤

1. 初始化指针：

   • left：指向数组的起始位置（索引0）。
   • right：指向数组的末尾位置（索引length - 1）。

2. 循环查找：

   • 当left小于或等于right时，执行以下步骤：
     1. 计算中间位置mid：mid = left + (right - left) / 2。这样可以避免直接相加可能导致的整数溢出。
     2. 比较中间元素array[mid]与目标值target：
        • 如果array[mid] == target，则找到目标元素，返回索引mid。
        • 如果array[mid] < target，说明目标元素在右半部分，更新left = mid + 1。
        • 如果array[mid] > target，说明目标元素在左半部分，更新right = mid - 1。

3. 未找到目标元素：

   • 如果循环结束后仍未找到目标元素，返回-1表示查找失败。

示例代码

public class BinarySearch {
    /**
     * 二分查找算法
     * @param array 已排序的数组
     * @param target 目标值
     * @return 目标值的索引，如果未找到则返回-1
     */
    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; // 未找到目标元素
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = 7;
        int result = binarySearch(sortedArray, target);

        if (result != -1) {
            System.out.println("目标元素 " + target + " 的索引是: " + result);
        } else {
            System.out.println("目标元素 " + target + " 未找到");
        }
    }
}

注意事项

1. 数组必须是有序的：二分查找的前提是数组已经排序。如果数组未排序，需要先进行排序操作。
2. 整数溢出问题：计算中间位置时，使用left + (right - left) / 2而不是(left + right) / 2，以避免整数溢出。
3. 时间复杂度：二分查找的时间复杂度为O(log n)，比线性查找的O(n)更高效，特别适用于大规模数据集。

通过以上步骤和示例代码，可以在Java中实现高效的二分查找算法。