冲刺阶段：二分查找边界条件处理精讲

在蓝桥杯的备赛过程中，二分查找算法是一个重要的知识点，尤其是在处理边界条件时。本文将深入探讨二分查找中的左闭右闭和左闭右开区间写法的差异，并演示如何查找第一个和最后一个元素的技巧。

一、二分查找简介

二分查找是一种高效的查找算法，适用于有序数组。其基本思想是通过不断缩小查找范围来快速定位目标元素。

二、左闭右闭与左闭右开区间的概念

左闭右闭区间：表示为 [left, right]，即 left 和 right 都包含在查找范围内。
左闭右开区间：表示为 [left, right)，即 left 包含在查找范围内，而 right 不包含。

三、写法差异及处理技巧

左闭右闭区间 `[left, right]`

在左闭右闭区间中，right 是有效的索引，因此在循环条件中可以使用 left <= right。

示例代码：

def binary_search_closed(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

左闭右开区间 `[left, right)`

在左闭右开区间中，right 不是有效的索引，因此在循环条件中只能使用 left < right。

示例代码：

def binary_search_open(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1

四、查找第一个和最后一个元素

在某些情况下，我们不仅需要找到目标元素，还需要找到其第一个或最后一个出现的位置。

查找第一个元素

示例代码：

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 继续向左查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

查找最后一个元素

示例代码：

def find_last(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            result = mid
            left = mid + 1  # 继续向右查找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result