Binary Search 在 Java 中的实现步骤

在Java中实现二分查找（Binary Search）通常涉及以下步骤：

1. 确定搜索范围：首先，你需要有一个已经排序的数组，因为二分查找只适用于有序数据。初始化两个指针，left 和 right，分别指向数组的起始位置和结束位置。

2. 计算中间索引：在每次迭代中，计算中间索引 mid。这通常通过 (left + right) / 2 来完成，但为了避免可能的整数溢出，更安全的做法是 left + (right - left) / 2。

3. 比较中间元素：将中间元素 array[mid] 与目标值 target 进行比较。

   • 如果 array[mid] 等于 target，则找到了目标值，返回 mid。
   • 如果 array[mid] 小于 target，则目标值只可能在数组的右半部分，更新 left 为 mid + 1。
   • 如果 array[mid] 大于 target，则目标值只可能在数组的左半部分，更新 right 为 mid - 1。

4. 重复步骤2和3：继续迭代，直到 left 超过 right，这意味着目标值不在数组中，返回一个表示未找到的值（通常是 -1）。

下面是一个简单的二分查找的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; // 目标值不在数组中
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(sortedArray, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

在这个例子中，binarySearch 方法实现了二分查找算法，main 方法提供了一个简单的测试用例。如果目标值存在于数组中，程序将打印出它的索引；如果不存在，将打印出一条消息说明元素未找到。