使用Java实现Binary Search算法在有序数组中查找指定元素

需求说明 #

给定一个有序整数数组，实现二分查找算法，接收数组和待查找元素作为输入，返回元素在数组中的索引；若元素不存在，返回-1。

实现代码 #

public class BinarySearch {
    public static int binarySearch(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // 计算中间索引，避免(left+right)直接相加导致的整数溢出
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == x) {
                // 找到目标元素，返回其索引
                return mid;
            } else if (arr[mid] < x) {
                // 目标在右半区间，缩小左边界
                left = mid + 1;
            } else {
                // 目标在左半区间，缩小右边界
                right = mid - 1;
            }
        }
        
        // 遍历完所有可能区间仍未找到，返回-1
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int x = 5;
        int result = binarySearch(arr, x);
        
        if (result == -1) {
            System.out.println("元素未找到");
        } else {
            System.out.println("元素找到，索引为 " + result);
        }
    }
}

算法逻辑与实现原理 #

核心逻辑 #

二分查找的核心是利用数组的有序性，每次将搜索范围缩小一半，相比线性查找（逐个遍历）的O(n)时间复杂度，二分查找的时间复杂度为O(log n)，数据量越大，效率提升越明显。

实现细节拆解 #

1. 初始化边界：用left标记当前搜索区间的左起点，right标记右终点，初始时覆盖整个数组。
2. 循环搜索：只要left <= right，说明当前区间还有元素可以搜索：
   • 计算中间索引mid：这里用left + (right - left)/2而非(left+right)/2，是为了避免当left和right都是较大整数时，二者相加超出Javaint类型的取值范围，引发溢出问题。
   • 匹配判断：
     • 如果arr[mid]等于目标元素，直接返回mid，查找完成。
     • 如果arr[mid]小于目标元素，说明目标在mid的右侧区间，因此将left更新为mid + 1（排除已比较过的mid位置）。
     • 如果arr[mid]大于目标元素，说明目标在mid的左侧区间，因此将right更新为mid - 1（同样排除mid位置）。
3. 未找到处理：当循环结束（left > right），说明整个数组都已排查完毕，目标元素不存在，返回-1。

测试示例说明 #

上述代码的main方法中，使用有序数组{1, 3, 5, 7, 9}查找元素5，运行后会输出元素找到，索引为 2；若将x改为2，则会输出元素未找到。

内容的提问来源于stack exchange，提问作者Piyush kag