讨论详情 - Online Judge

Python
Python 二分三兄弟教程
admin SU @ 2025-4-26 13:35:13

Python 二分查找教程

二分查找（Binary Search）是一种高效的查找算法，用于在有序数组中查找目标值。其核心思想是通过不断将查找范围减半来快速定位目标值的位置。

二分查找的基本原理

前提条件：数组必须是有序的（升序或降序）。
步骤：
- 确定数组的中间位置 mid。
- 比较目标值 target 和 mid 的值：
  - 如果 target == mid，找到目标值，返回索引。
  - 如果 target < mid，说明目标值在左半部分，继续在左半部分查找。
  - 如果 target > mid，说明目标值在右半部分，继续在右半部分查找。
- 重复上述步骤，直到找到目标值或者查找范围为空。
时间复杂度：O(log n)，比线性查找（O(n)）高效得多。

Python 实现二分查找

以下是几种常见的实现方式：

1. 递归实现

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # 目标值不存在
    
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, right)

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"目标值 {target} 的索引是: {result}")

2. 迭代实现

def binary_search_iterative(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:
            right = mid - 1
        else:
            left = mid + 1
    
    return -1  # 目标值不存在

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search_iterative(arr, target)
print(f"目标值 {target} 的索引是: {result}")

3. 使用内置函数 `bisect`

Python 提供了 bisect 模块，可以方便地实现二分查找。它主要用于插入元素时保持列表有序，但也可以用来查找目标值的位置。

import bisect

def binary_search_bisect(arr, target):
    # 找到目标值应该插入的位置
    index = bisect.bisect_left(arr, target)
    if index < len(arr) and arr[index] == target:
        return index
    return -1

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 7
result = binary_search_bisect(arr, target)
print(f"目标值 {target} 的索引是: {result}")

注意事项

数组必须有序：如果数组无序，需要先排序（例如使用 sorted() 或 .sort() 方法），但这会增加时间复杂度。
边界条件：注意处理空数组、目标值不在数组中的情况。
整数溢出：在某些语言中（如 C++），计算 (left + right) // 2 可能导致整数溢出。但在 Python 中，整数类型是动态扩展的，因此不会发生溢出问题。

示例运行

假设有一个有序数组 [1, 3, 5, 7, 9, 11]，目标值为 7：

第一次查找：mid = (0 + 5) // 2 = 2，arr[2] = 5，目标值大于 5，缩小范围到 [7, 9, 11]。
第二次查找：mid = (3 + 5) // 2 = 4，arr[4] = 9，目标值小于 9，缩小范围到 [7]。
第三次查找：mid = (3 + 3) // 2 = 3，arr[3] = 7，找到目标值。

最终返回索引 3。

练习题

在一个有序数组中查找目标值，并返回其索引。如果目标值不存在，返回 -1。
给定一个有序数组和一个目标值，找到目标值的插入位置，使得插入后数组仍然有序。
在旋转排序数组中查找目标值（变种问题）。

希望这篇教程对你有帮助！如果有任何问题，请随时提问！

admin SU @ 2025-4-26 13:57:49
为了更好地理解 Lower Bound 和 Upper Bound 的查找过程，我们通过几个数据例子逐步演示它们的运行逻辑。以下是一个有序数组 [1, 3, 5, 7, 9, 11]，我们将对不同的目标值进行查找。

示例数组
```
arr = [1, 3, 5, 7, 9, 11]
```
目标值 1：查找 target = 6

1. Lower Bound 查找
- 目标：找到第一个大于或等于 6 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，满足 arr[mid] >= target，所以更新 right = mid = 3
  
  第二次迭代：
  
  mid = (0 + 3) // 2 = 1
  
  arr[1] = 3，不满足 arr[mid] >= target，所以更新 left = mid + 1 = 2
  
  第三次迭代：
  
  mid = (2 + 3) // 2 = 2
  
  arr[2] = 5，不满足 arr[mid] >= target，所以更新 left = mid + 1 = 3
  
  循环结束：left = right = 3
- 结果：Lower Bound 返回索引 3（即元素 7 的位置）。
2. Upper Bound 查找
- 目标：找到第一个严格大于 6 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，满足 arr[mid] > target，所以更新 right = mid = 3
  
  第二次迭代：
  
  mid = (0 + 3) // 2 = 1
  
  arr[1] = 3，不满足 arr[mid] > target，所以更新 left = mid + 1 = 2
  
  第三次迭代：
  
  mid = (2 + 3) // 2 = 2
  
  arr[2] = 5，不满足 arr[mid] > target，所以更新 left = mid + 1 = 3
  
  循环结束：left = right = 3
- 结果：Upper Bound 返回索引 3（即元素 7 的位置）。
目标值 2：查找 target = 5

1. Lower Bound 查找
- 目标：找到第一个大于或等于 5 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，满足 arr[mid] >= target，所以更新 right = mid = 3
  
  第二次迭代：
  
  mid = (0 + 3) // 2 = 1
  
  arr[1] = 3，不满足 arr[mid] >= target，所以更新 left = mid + 1 = 2
  
  第三次迭代：
  
  mid = (2 + 3) // 2 = 2
  
  arr[2] = 5，满足 arr[mid] >= target，所以更新 right = mid = 2
  
  循环结束：left = right = 2
- 结果：Lower Bound 返回索引 2（即元素 5 的位置）。
2. Upper Bound 查找
- 目标：找到第一个严格大于 5 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，满足 arr[mid] > target，所以更新 right = mid = 3
  
  第二次迭代：
  
  mid = (0 + 3) // 2 = 1
  
  arr[1] = 3，不满足 arr[mid] > target，所以更新 left = mid + 1 = 2
  
  第三次迭代：
  
  mid = (2 + 3) // 2 = 2
  
  arr[2] = 5，不满足 arr[mid] > target，所以更新 left = mid + 1 = 3
  
  循环结束：left = right = 3
- 结果：Upper Bound 返回索引 3（即元素 7 的位置）。
目标值 3：查找 target = 12

1. Lower Bound 查找
- 目标：找到第一个大于或等于 12 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，不满足 arr[mid] >= target，所以更新 left = mid + 1 = 4
  
  第二次迭代：
  
  mid = (4 + 6) // 2 = 5
  
  arr[5] = 11，不满足 arr[mid] >= target，所以更新 left = mid + 1 = 6
  
  循环结束：left = right = 6
- 结果：Lower Bound 返回索引 6（即插入到数组末尾的位置）。
2. Upper Bound 查找
- 目标：找到第一个严格大于 12 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，不满足 arr[mid] > target，所以更新 left = mid + 1 = 4
  
  第二次迭代：
  
  mid = (4 + 6) // 2 = 5
  
  arr[5] = 11，不满足 arr[mid] > target，所以更新 left = mid + 1 = 6
  
  循环结束：left = right = 6
- 结果：Upper Bound 返回索引 6（即插入到数组末尾的位置）。
目标值 4：查找 target = 0

1. Lower Bound 查找
- 目标：找到第一个大于或等于 0 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，满足 arr[mid] >= target，所以更新 right = mid = 3
  
  第二次迭代：
  
  mid = (0 + 3) // 2 = 1
  
  arr[1] = 3，满足 arr[mid] >= target，所以更新 right = mid = 1
  
  第三次迭代：
  
  mid = (0 + 1) // 2 = 0
  
  arr[0] = 1，满足 arr[mid] >= target，所以更新 right = mid = 0
  
  循环结束：left = right = 0
- 结果：Lower Bound 返回索引 0（即元素 1 的位置）。
2. Upper Bound 查找
- 目标：找到第一个严格大于 0 的位置。
- 步骤：
  
  初始范围：left = 0, right = 6
  
  第一次迭代：
  
  mid = (0 + 6) // 2 = 3
  
  arr[3] = 7，满足 arr[mid] > target，所以更新 right = mid = 3
  
  第二次迭代：
  
  mid = (0 + 3) // 2 = 1
  
  arr[1] = 3，满足 arr[mid] > target，所以更新 right = mid = 1
  
  第三次迭代：
  
  mid = (0 + 1) // 2 = 0
  
  arr[0] = 1，满足 arr[mid] > target，所以更新 right = mid = 0
  
  循环结束：left = right = 0
- 结果：Upper Bound 返回索引 0（即元素 1 的位置）。
总结

通过上述例子可以看出：
- Lower Bound 总是返回第一个 大于或等于目标值 的位置。
- Upper Bound 总是返回第一个 严格大于目标值 的位置。
- 如果目标值不存在于数组中，两者都会返回一个合适的插入点以保持数组有序。
希望这些例子能帮助你更好地理解 Lower Bound 和 Upper Bound 的工作原理！

👀 1

🤡 1
admin SU @ 2025-4-26 13:56:35
在讨论二分查找(Binary Search)、Lower Bound和Upper Bound时，我们实际上是在探讨几种不同的但相互关联的搜索算法，它们都在有序数组中高效地定位元素或确定插入位置。下面详细解释这三种技术，并展示它们的区别和联系。

1. Binary Search (二分查找)

目的：在一个有序数组中找到一个特定的目标值的位置。如果目标值存在于数组中，则返回其索引；否则返回-1表示未找到。

基本步骤：
- 初始化左右指针（通常为数组的起始和结束位置）。
- 计算中间位置 mid，比较中间元素与目标值。
- 如果中间元素等于目标值，返回 mid。
- 如果中间元素小于目标值，说明目标值位于右半部分，更新左指针。
- 如果中间元素大于目标值，说明目标值位于左半部分，更新右指针。
- 当左右指针相遇且没有找到目标值时，返回-1。
示例代码：
```
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
```
2. Lower Bound

目的：找到第一个大于或等于目标值的元素的位置。如果目标值不存在于数组中，它会返回目标值应该插入的位置，以保持数组的有序性。

基本步骤：
- 类似于二分查找，但当发现中间元素小于目标值时才移动左边界，其他情况下都尝试缩小右边界。
- 最终，left 指针指向的是第一个大于或等于目标值的元素的位置。
示例代码：
```
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left
```
3. Upper Bound

目的：找到第一个严格大于目标值的元素的位置。类似于Lower Bound，但如果目标值不在数组中，它同样返回目标值应插入的位置，以维持升序。

基本步骤：
- 和Lower Bound相似，但在判断条件上有所不同。只有当中间元素小于或等于目标值时才移动左边界。
- 最终，left 指针指向的是第一个严格大于目标值的元素的位置。
示例代码：
```
def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left
```
区别与联系
- Binary Search 主要用于查找是否存在某个确切的值，并返回其位置。
- Lower Bound 查找第一个不小于给定值的位置，无论该值是否存在于数组中。
- Upper Bound 查找第一个大于给定值的位置，这对于需要知道如何保持数组有序非常有用。
例如，在一个排序数组 [1, 3, 5, 7, 9, 11] 中：
- 使用 binary_search(5) 返回 2，即数字 5 的索引。
- 使用 lower_bound(6) 返回 3，因为 7 是第一个不小于 6 的数。
- 使用 upper_bound(5) 返回 3，因为 7 是第一个严格大于 5 的数。
通过理解这三个概念，你可以更灵活地处理各种涉及有序数组的问题，无论是查找特定元素、统计元素出现次数还是决定新元素的插入位置。这些技术广泛应用于各种数据结构和算法挑战中，是提高效率的重要工具。
admin SU @ 2025-4-26 13:51:15
Upper Bound 和 Lower Bound 的原理、思想、过程和步骤

Upper Bound 和 Lower Bound 是二分查找算法的两个重要变种，主要用于在有序数组中高效地定位元素或确定插入位置。下面将详细解释它们的原理、思想、过程和具体步骤。

一、Lower Bound

1. 原理与思想
- 定义：Lower Bound 用于在一个有序数组中找到第一个大于或等于目标值的位置。
- 思想：通过不断缩小搜索范围，直到找到一个满足条件的最小索引。即使目标值不存在于数组中，也能返回一个有效的插入点以保持数组有序。
2. 过程与步骤
1. 初始化左右边界：left = 0，right = len(arr)。
2. 进入循环，条件是 left < right：
  
  计算中间位置：mid = (left + right) // 2。
  
  如果 arr[mid] < target，说明目标值位于右半部分，更新 left = mid + 1。
  
  否则（即 arr[mid] >= target），目标值可能位于左半部分或正好是 mid，更新 right = mid。
3. 循环结束时，left 即为所求的位置，表示第一个大于或等于目标值的元素索引。
示例代码：
```
def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left
```
二、Upper Bound

1. 原理与思想
- 定义：Upper Bound 用于在一个有序数组中找到第一个严格大于目标值的位置。
- 思想：类似于 Lower Bound，但其目的是寻找第一个严格大于目标值的位置。同样，如果目标值不在数组中，返回的是一个合适的插入点。
2. 过程与步骤
1. 初始化左右边界：left = 0，right = len(arr)。
2. 进入循环，条件是 left < right：
  
  计算中间位置：mid = (left + right) // 2。
  
  如果 arr[mid] <= target，说明目标值位于右半部分，更新 left = mid + 1。
  
  否则（即 arr[mid] > target），目标值可能位于左半部分或正好是 mid，更新 right = mid。
3. 循环结束时，left 即为所求的位置，表示第一个严格大于目标值的元素索引。
示例代码：
```
def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left
```
三、比较与总结
- 搜索条件区别：
  
  Lower Bound 查找第一个大于或等于目标值的位置。
  
  Upper Bound 查找第一个严格大于目标值的位置。
- 应用场景：
  
  使用 Lower Bound 可以确定某个数是否存在，并获取其索引；也可以确定该数的插入位置以维持数组的有序性。
  
  结合 Lower Bound 和 Upper Bound 可以计算某数在数组中的出现次数（通过 upper_bound - lower_bound）。
- 实现上的细微差别主要在于判断条件的不同，这决定了它们各自的应用场景。
通过理解这两个概念及其背后的逻辑，可以更灵活地处理涉及有序数据结构的各种问题，如快速查找、插入以及统计特定值的数量等。无论是手动实现还是利用 Python 标准库中的 bisect_left 和 bisect_right 函数，这些技术都提供了强大的工具来优化操作效率。
admin SU @ 2025-4-26 13:49:21
Upper Bound 和 Lower Bound 的原理在二分查找算法中，Upper Bound 和 Lower Bound 是两个非常有用的变种，它们用于在有序数组中找到特定值的位置或确定插入点。下面详细解释这两个概念的原理及其区别。
1. Lower Bound 定义：在一个有序数组中，Lower Bound 是指找到第一个大于或等于目标值的元素的位置。如果目标值不存在于数组中，它返回的是目标值应该插入的位置，以保持数组的有序性。
实现逻辑：

初始化左右边界 left = 0 和 right = len(arr)。进入循环直到 left < right：计算中间位置 mid = (left + right) // 2。如果 arr[mid] < target，说明目标值位于右半部分，更新 left = mid + 1。否则（即 arr[mid] >= target），目标值可能位于左半部分或正好是 mid，更新 right = mid。最终，left 即为所求的位置，表示第一个大于或等于目标值的元素索引。应用场景：

查找一个数是否存在，并获取其索引。确定一个数在数组中的插入位置，确保数组依然有序。 2. Upper Bound 定义：在一个有序数组中，Upper Bound 是指找到第一个严格大于目标值的元素的位置。如果目标值不存在于数组中，它同样返回目标值应插入的位置，但这次是为了让数组维持升序。

实现逻辑：

初始化左右边界 left = 0 和 right = len(arr)。进入循环直到 left < right：计算中间位置 mid = (left + right) // 2。如果 arr[mid] <= target，说明目标值位于右半部分，更新 left = mid + 1。否则（即 arr[mid] > target），目标值可能位于左半部分或正好是 mid，更新 right = mid。最终，left 即为所求的位置，表示第一个严格大于目标值的元素索引。应用场景：

查找一个数是否存在，并获取其索引（结合 Lower Bound 使用）。确定一个数在数组中的插入位置，确保数组依然有序。结合 Lower Bound 来统计数组中某个数的出现次数。两者之间的主要区别搜索条件： Lower Bound 搜索第一个大于或等于目标值的元素。 Upper Bound 搜索第一个严格大于目标值的元素。返回值： Lower Bound 返回的目标值插入点保证了所有左边的元素都小于目标值。 Upper Bound 返回的目标值插入点保证了所有左边的元素都不大于目标值。使用场景：当需要知道某个数是否存在于数组中时，可以使用 Lower Bound 或 Upper Bound 判断。要统计某个数在数组中的出现次数，可以通过 Upper Bound - Lower Bound 实现。通过理解这两个概念，我们可以更高效地处理与排序数组相关的查询问题，无论是寻找元素、确定插入位置还是统计元素出现次数。这些技术广泛应用于各种数据结构和算法挑战中。
admin SU @ 2025-4-26 13:46:23
Python 实现 Upper Bound 二分查找教程

Upper Bound 是一种特殊的二分查找，用于在有序数组中找到第一个严格大于目标值的位置。即使目标值不存在于数组中，Upper Bound 也能返回一个有效的插入位置，使得数组仍然保持有序。

什么是 Upper Bound？
- 定义：Upper Bound 是指在一个有序数组中，找到第一个严格大于目标值的元素的索引。
- 用途：
  
  查找目标值是否存在（结合 Lower Bound）。
  
  确定目标值的插入位置（保持数组有序）。
  
  统计目标值在数组中的出现次数（通过 Upper Bound - Lower Bound）。
Python 实现 Upper Bound

以下是几种实现方式：

1. 迭代实现
```
def upper_bound(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1  # 目标值在右半部分
        else:
            right = mid  # 目标值可能在左半部分，或者就是当前 mid
    
    return left  # 返回第一个 > target 的位置

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 6
result = upper_bound(arr, target)
print(f"目标值 {target} 的 Upper Bound 索引是: {result}")
```
解释：
- 如果 arr[mid] <= target，说明目标值不可能在左侧，因此将 left 移动到 mid + 1。
- 否则，目标值可能在左侧，或者就是当前 mid，因此将 right 移动到 mid。
- 最终，left 和 right 相遇时，left 就是第一个严格大于目标值的位置。
2. 递归实现
```
def upper_bound_recursive(arr, target, left, right):
    if left >= right:
        return left  # 返回第一个 > target 的位置
    
    mid = (left + right) // 2
    if arr[mid] <= target:
        return upper_bound_recursive(arr, target, mid + 1, right)
    else:
        return upper_bound_recursive(arr, target, left, mid)

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 6
result = upper_bound_recursive(arr, target, 0, len(arr))
print(f"目标值 {target} 的 Upper Bound 索引是: {result}")
```
3. 使用内置函数 bisect_right

Python 的 bisect 模块提供了 bisect_right 函数，直接实现了 Upper Bound 的功能。
```
import bisect

def upper_bound_bisect(arr, target):
    return bisect.bisect_right(arr, target)

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 6
result = upper_bound_bisect(arr, target)
print(f"目标值 {target} 的 Upper Bound 索引是: {result}")
```
运行示例

假设有一个有序数组 [1, 3, 5, 7, 9, 11]，目标值为 6：
- 第一次查找：mid = (0 + 5) // 2 = 2，arr[2] = 5，目标值大于等于 5，缩小范围到 [7, 9, 11]。
- 第二次查找：mid = (3 + 5) // 2 = 4，arr[4] = 9，目标值小于 9，缩小范围到 [7]。
- 最终返回索引 3，即第一个严格大于 6 的位置。
如果目标值为 10，最终返回索引 5，表示应该插入到数组末尾。

注意事项
1. 数组必须有序：Upper Bound 要求输入数组是升序排列的。
2. 边界条件：
  
  如果目标值小于数组中的最小值，返回 0。
  
  如果目标值大于或等于数组中的最大值，返回数组长度（即插入到最后）。
3. 与 Lower Bound 的区别：
  
  Lower Bound 找到的是第一个大于或等于目标值的位置。
  
  Upper Bound 找到的是第一个严格大于目标值的位置。
统计目标值出现次数

结合 Lower Bound 和 Upper Bound，可以轻松统计目标值在数组中的出现次数：
```
def count_occurrences(arr, target):
    lower = lower_bound(arr, target)
    upper = upper_bound(arr, target)
    return upper - lower

# 测试代码
arr = [1, 3, 5, 5, 5, 7, 9, 11]
target = 5
count = count_occurrences(arr, target)
print(f"目标值 {target} 在数组中出现了 {count} 次")
```
练习题
1. 在一个有序数组中，使用 Upper Bound 查找目标值，并判断目标值是否存在。
2. 给定一个有序数组和多个目标值，批量计算每个目标值的 Upper Bound。
3. 结合 Lower Bound 和 Upper Bound，统计目标值在数组中的出现次数。
希望这篇教程对你有帮助！如果有任何问题，请随时提问！
admin SU @ 2025-4-26 13:40:05
Python 实现 Lower Bound 二分查找教程

Lower Bound 是一种特殊的二分查找，用于在有序数组中找到第一个大于或等于目标值的位置。即使目标值不存在于数组中，Lower Bound 也能返回一个有效的插入位置，使得数组仍然保持有序。

什么是 Lower Bound？
- 定义：Lower Bound 是指在一个有序数组中，找到第一个大于或等于目标值的元素的索引。
- 用途：
  
  查找目标值是否存在。
  
  确定目标值的插入位置（保持数组有序）。
  
  解决一些变种问题，如旋转数组中的查找。
Python 实现 Lower Bound

以下是几种实现方式：

1. 迭代实现
```
def lower_bound(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1  # 目标值在右半部分
        else:
            right = mid  # 目标值可能在左半部分，或者就是当前 mid
    
    return left  # 返回第一个 >= target 的位置

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 6
result = lower_bound(arr, target)
print(f"目标值 {target} 的 Lower Bound 索引是: {result}")
```
解释：
- 如果 arr[mid] < target，说明目标值不可能在左侧，因此将 left 移动到 mid + 1。
- 否则，目标值可能在左侧，或者就是当前 mid，因此将 right 移动到 mid。
- 最终，left 和 right 相遇时，left 就是第一个大于或等于目标值的位置。
2. 递归实现
```
def lower_bound_recursive(arr, target, left, right):
    if left >= right:
        return left  # 返回第一个 >= target 的位置
    
    mid = (left + right) // 2
    if arr[mid] < target:
        return lower_bound_recursive(arr, target, mid + 1, right)
    else:
        return lower_bound_recursive(arr, target, left, mid)

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 6
result = lower_bound_recursive(arr, target, 0, len(arr))
print(f"目标值 {target} 的 Lower Bound 索引是: {result}")
```
3. 使用内置函数 bisect_left

Python 的 bisect 模块提供了 bisect_left 函数，直接实现了 Lower Bound 的功能。
```
import bisect

def lower_bound_bisect(arr, target):
    return bisect.bisect_left(arr, target)

# 测试代码
arr = [1, 3, 5, 7, 9, 11]
target = 6
result = lower_bound_bisect(arr, target)
print(f"目标值 {target} 的 Lower Bound 索引是: {result}")
```
运行示例

假设有一个有序数组 [1, 3, 5, 7, 9, 11]，目标值为 6：
- 第一次查找：mid = (0 + 5) // 2 = 2，arr[2] = 5，目标值大于 5，缩小范围到 [7, 9, 11]。
- 第二次查找：mid = (3 + 5) // 2 = 4，arr[4] = 9，目标值小于 9，缩小范围到 [7]。
- 最终返回索引 3，即第一个大于或等于 6 的位置。
如果目标值为 10，最终返回索引 5，表示应该插入到数组末尾。

注意事项
1. 数组必须有序：Lower Bound 要求输入数组是升序排列的。
2. 边界条件：
  
  如果目标值小于数组中的最小值，返回 0。
  
  如果目标值大于数组中的最大值，返回数组长度（即插入到最后）。
3. 与 Upper Bound 的区别：
  
  Lower Bound 找到的是第一个大于或等于目标值的位置。
  
  Upper Bound 找到的是第一个大于目标值的位置。
练习题
1. 在一个有序数组中，使用 Lower Bound 查找目标值，并判断目标值是否存在。
2. 给定一个有序数组和多个目标值，批量计算每个目标值的 Lower Bound。
3. 结合 Upper Bound，统计目标值在数组中的出现次数。
希望这篇教程对你有帮助！如果有任何问题，请随时提问！

Python 二分三兄弟教程

Python 二分查找教程

二分查找的基本原理

Python 实现二分查找

1. 递归实现

2. 迭代实现

3. 使用内置函数 bisect

注意事项

示例运行

练习题

6 条评论

示例数组

目标值 1：查找 target = 6

1. Lower Bound 查找

2. Upper Bound 查找

目标值 2：查找 target = 5

1. Lower Bound 查找

2. Upper Bound 查找

目标值 3：查找 target = 12

1. Lower Bound 查找

2. Upper Bound 查找

目标值 4：查找 target = 0

1. Lower Bound 查找

2. Upper Bound 查找

总结

1. Binary Search (二分查找)

2. Lower Bound

3. Upper Bound

区别与联系

Upper Bound 和 Lower Bound 的原理、思想、过程和步骤

一、Lower Bound

二、Upper Bound

三、比较与总结

Python 实现 Upper Bound 二分查找教程

什么是 Upper Bound？

Python 实现 Upper Bound

1. 迭代实现

2. 递归实现

3. 使用内置函数 bisect_right

运行示例

注意事项

统计目标值出现次数

练习题

Python 实现 Lower Bound 二分查找教程

什么是 Lower Bound？

Python 实现 Lower Bound

1. 迭代实现

2. 递归实现

3. 使用内置函数 bisect_left

运行示例

注意事项

练习题

状态

开发

支持

还没有账户？

登录

3. 使用内置函数 `bisect`

目标值 1：查找 `target = 6`

目标值 2：查找 `target = 5`

目标值 3：查找 `target = 12`

目标值 4：查找 `target = 0`

3. 使用内置函数 `bisect_right`

3. 使用内置函数 `bisect_left`