什么是java二分搜索

Java 中的二分搜索（Binary Search） 是一种在有序数组或集合中高效查找目标元素的算法。

一、基本概念

核心思想：

• 每次将查找范围对半分
• 根据中间元素与目标值的大小关系，决定继续在左半部分还是右半部分查找
• 不断缩小范围，直到找到或确认不存在

时间复杂度：

• 最优：O(1)
• 平均 / 最差：O(log n)

前提条件：

• 数据必须有序（升序或降序）

二、原理示意（升序数组）

假设数组：

[1, 3, 5, 7, 9, 11]

查找 7：

1. left = 0, right = 5, mid = 2 → 5 < 7 → 向右
2. left = 3, right = 5, mid = 4 → 9 > 7 → 向左
3. left = 3, right = 3, mid = 3 → 7 == 7 ✅ 找到

三、Java 手写二分搜索示例

public class BinarySearchExample {
    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) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        System.out.println(binarySearch(arr, 7)); // 输出 3
    }
}

四、使用 Java 标准库（推荐）

1. 数组

import java.util.Arrays;

int[] arr = {1, 3, 5, 7, 9};
int index = Arrays.binarySearch(arr, 5); // 返回索引

2. List（如 ArrayList）

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

List<Integer> list = new ArrayList<>();
Collections.sort(list); // 必须先排序
int index = Collections.binarySearch(list, 5);

⚠️ 注意：使用标准库前，集合必须已排序，否则结果不确定。

五、常见应用场景

• 在有序数据中查找元素
• 判断某个值是否存在
• 查找边界（第一个 ≥ target 的位置）
• 算法题中的优化手段（如搜索答案）

六、小结

如果你愿意，我也可以讲二分搜索的变种（左边界 / 右边界）或常见面试题。