分而治之算法示例

分而治之算法是一种高效的算法设计思想，通过将复杂问题分解为更小的、相似的子问题来解决。以下是一些经典的分而治之算法示例：

经典示例

快速排序（Quick Sort） 快速排序是一种使用分而治之策略的排序算法。它通过选择一个“基准”元素，将数组分为两个子数组，一个包含小于基准的元素，另一个包含大于基准的元素，然后递归地对这两个子数组进行排序。
```
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
```

归并排序（Merge Sort） 归并排序是一种将数组分成两半，递归地排序两半，然后将排序后的两半合并的排序算法。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

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

二分查找（Binary Search） 二分查找算法通过将有序数组分成两半，递归地查找目标值，从而实现高效查找。

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

扩展阅读

更多关于分而治之算法的示例和深入理解，可以参考本站的分而治之算法教程。