二分查找算法

代码解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def binary_search(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(arr, target, left, mid - 1)
    # 递归条件：目标值在右半部分
    else:
        return binary_search(arr, target, mid + 1, right)

我的解释

其实这里的算法解释和上次学习的递归关系很大

而且我感觉，大部分的数学问题都可以使用递归解决，这本来就是一种数学思想

分而治之 ！！！这就是数学思想

这里的markdown的语法来自菜鸟教学

还有就是分享周杰伦的歌真的很好听

快速排序

D&C

这里是对D&C的解释:

归并排序（Merge Sort）
将数组分成两半，递归排序，再将两个有序数组合并。

快速排序（Quick Sort）
选择一个基准元素，将数组分为小于基准和大于基准的两部分，递归排序。

二分查找（Binary Search）
将有序数组分为两半，递归查找目标值。

大整数乘法
将大整数分解为更小的部分，递归计算后再合并结果。

矩阵乘法（Strassen算法）
将矩阵分解为子矩阵，递归计算后再合并。

最近点对问题
将平面上的点集分为两半，递归求解最近点对，再合并结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def merge_sort(arr):
    # 基线条件：数组长度为1或0时直接返回
    if len(arr) <= 1:
        return arr
    
    # 分解：将数组分为两半
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # 递归解决左半部分
    right_half = merge_sort(arr[mid:])  # 递归解决右半部分
    
    # 合并：将两个有序数组合并
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    # 合并两个有序数组
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 将剩余部分加入结果
    result.extend(left[i:])
    result.extend(right[j:])
    return result
1
2
3
4
5
6
7
8
9
def quicksort(array): 
    if len(array) < 2: 
        return array 
    else: 
        pivot = array[0] 
        less = [i for i in array[1:] if i <= pivot] 
        greater = [i for i in array[1:] if i > pivot] 
    return quicksort(less) + [pivot] + quicksort(greater) 
print quicksort([10, 5, 2, 3])

先设置一个基准值[pivot]然后以此为基准分为大于和小于的两个子集合，对子集合再进行递归运算。

刚才你大致见识了归纳证明！归纳证明是一种证明算法行之有效的方式，它分两步：基线
条件和归纳条件。是不是有点似曾相识的感觉？例如，假设我要证明我能爬到梯子的最上面。
递归条件是这样的：如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果我站
在第二个横档上，就能爬到第三个横档。这就是归纳条件。而基线条件是这样的，即我已经站
在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。
对于快速排序，可使用类似的推理。在基线条件中，我证明这种算法对空数组或包含一个
元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两
个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，
以此类推。因此，我可以说，快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明，
但它很有趣，并与D&C协同发挥作用

序号 问题 简要说明
1 二分查找算法的基线条件和递归条件是什么？ 解释了二分查找的基线条件（终止递归）和递归条件（继续递归）。
2 D&C（分治法）是什么？ 介绍了分治法的定义、步骤、特点、经典应用以及与动态规划的区别。
3 用 Markdown 文法输出分治法的说明。 使用 Markdown 语法整理了分治法的详细说明。
4 Markdown 如何表示 Python 代码？ 解释了如何在 Markdown 中使用代码块和行内代码表示 Python 代码。
5 快速排序代码的修正与优化。 修正了快速排序代码的缩进和 print 语法问题，并提供了优化建议。
6 将以上问题制作成表格，内容尽量精简。 将你问过的问题整理成表格，内容精简明了。
7 要用 Markdown 语法给我输出。 使用 Markdown 语法生成表格，内容为你问过的问题。

以上是我在学习过程中向ai提问的问题!!!