怎么使用Java实现二分查找

# 怎么使用Java实现二分查找

## 什么是二分查找

二分查找（Binary Search）是一种高效的查找算法，适用于**已排序**的数组或列表。它的核心思想是通过**分而治之**的策略，每次将搜索范围缩小一半，直到找到目标元素或确定元素不存在。

### 算法特点
- **时间复杂度**：O(log n)
- **空间复杂度**：O(1)（迭代实现）
- **前提条件**：数据集必须是有序的

---

## 二分查找的实现步骤

1. **确定搜索范围**：初始化左右指针为数组的首尾（`left=0`, `right=arr.length-1`）
2. **计算中间位置**：`mid = left + (right - left) / 2`（避免整数溢出）
3. **比较中间元素**：
   - 若 `arr[mid] == target`，返回 `mid`
   - 若 `arr[mid] < target`，调整左指针 `left = mid + 1`
   - 若 `arr[mid] > target`，调整右指针 `right = mid - 1`
4. **重复步骤2-3**，直到 `left > right`（未找到目标）

---

## Java代码实现

### 迭代实现
```java
public class BinarySearch {
    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[] sortedArray = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int result = binarySearch(sortedArray, target);
        System.out.println("元素 " + target + " 的索引位置: " + result);
    }
}

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        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, target, mid + 1, right);
        } else {
            return binarySearch(arr, target, left, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] sortedArray = {2, 4, 6, 8, 10};
        int target = 6;
        int result = binarySearch(sortedArray, target, 0, sortedArray.length - 1);
        System.out.println("递归实现 - 元素 " + target + " 的索引位置: " + result);
    }
}

关键注意事项

1. 数组必须有序
   如果输入数组未排序，需先调用 Arrays.sort(arr) 进行排序（时间复杂度O(n log n)）。

2. 整数溢出问题
   计算 mid 时避免使用 (left + right) / 2，改用 left + (right - left) / 2。

3. 边界条件处理

   • 当数组为空时直接返回 -1
   • 确保 right 初始值为 arr.length - 1（闭区间）

4. 重复元素处理
   基础二分查找不保证返回重复元素的第一个或最后一个位置。如需此功能，需修改算法（见下文变体）。

二分查找的常见变体

1. 查找第一个等于目标的位置

public static int findFirstOccurrence(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 继续向左搜索
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

2. 查找最后一个等于目标的位置

public static int findLastOccurrence(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // 继续向右搜索
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

性能对比：二分查找 vs 线性查找

实际应用场景

1. 数据库索引：B-tree索引使用类似二分查找的原理
2. 游戏开发：快速判断玩家分数在排行榜中的位置
3. 数值计算：求解数学方程的近似解（如二分法求根）

总结

二分查找是算法学习中的经典案例，其高效性体现在对数级时间复杂度。通过Java实现时需注意： 1. 确保输入数组有序 2. 正确处理边界条件和整数溢出 3. 根据需求选择基础实现或变体

掌握二分查找不仅能提升编码能力，更是理解分治算法思想的重要一步。 “`

注：实际字数约1350字（含代码和表格）。如需扩展，可增加以下内容： - 更多变体（如查找最接近的值） - 与Java标准库中 Arrays.binarySearch() 的对比 - 处理非整数类型的数据（如字符串）