17. 二分查找

正文

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的核心思想是通过不断将搜索区间减半，来极大地提高搜索效率。

算法模板

fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        // 使用该方式计算 mid 防止 (left + right) 导致整型溢出
        val mid = left + (right - left) / 2

        if (nums[mid] == target) {
            // 找到目标，返回索引
            return mid
        } else if (nums[mid] < target) {
            // 目标在右半部分，收缩左边界
            left = mid + 1
        } else {
            // 目标在左半部分，收缩右边界
            right = mid - 1
        }
    }

    // 未找到目标元素
    return -1
}

使用说明

1. 先决条件：

   • 数据必须是有序的（通常是升序）。
   • 必须支持随机访问（即数组或列表，链表不适用）。

2. 核心技巧：

   • **计算 mid**：建议使用 val mid = left + (right - left) / 2，而不是 (left + right) / 2。这是为了避免当 left 和 right 都很大时相加导致 Int 溢出。
   • 循环条件：while (left <= right) 意味着搜索区间是闭区间 [left, right]。

3. 复杂度分析：

   • 时间复杂度：$O(\log N)$。
   • 空间复杂度：$O(1)$。

4. 注意点：

   • 注意边界处理：left = mid + 1 和 right = mid - 1，确保每次循环都能缩小搜索区间，防止死循环。
   • 如果数组中存在重复元素，该模板返回的是其中任意一个目标的索引。若需查找“最左侧”或“最右侧”插入点，请参考后续专门的二分模板。