二分查找（Binary Search）

二分查找（Binary Search）

✅ 算法介绍

二分查找是一种在有序数组中查找目标值的高效算法。其基本思想是：每次将查找范围缩小一半，直到找到目标元素或范围为空为止。

🧭 适用场景

• 在 有序数组/列表 中查找目标值
• 用于优化一些决策类问题的“最小值/最大值”边界（如：最小化最大值）
• 多用于配合判定函数的 答案二分法

⏱️ 时间复杂度 & 空间复杂度

类别	复杂度
时间复杂度	O(log n)
空间复杂度	O(1)（迭代） / O(log n)（递归）

---

🐍 Python 实现

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 找到目标，返回索引
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到目标

---

☕ Java 实现

public int binarySearch(int[] arr, int target) {
    int left = 0, 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;
}

---

🐹 Go 实现

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        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
}

---

🌐 JavaScript 实现

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

---

🧵 C 实现

int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 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;
}

---

🧠 C++ 实现

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 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;
}

---

✨ 小提示

• 注意终止条件是 left <= right，不是 <
• 使用 mid = left + (right - left) / 2 可以防止溢出
• 如果查找的是边界（第一个/最后一个出现位置），需要做进一步判断和收缩方式调整
• 二分查找的本质是对单调性函数做“答案查找”，很多算法题都能转化为二分解法