蓝桥杯丨分治算法

前言

初识分治算法，运用分治算法解决简单问题。

二分查找

在查找的时候，我们学习过二分查找，其实就运用了分治思想。每次将待排序序列折半进行查找，直到找到相应的元素，当然，查找的元素也可能不存在，具体算法如下：

nums=[1,2,3,4,5]
def search(l,r,nums,target):
    while l<=r:
        mid=(l+r)//2
        if nums[mid]<target:
            l=mid+1
        elif nums[mid]>target:
            r=mid-1
        else:
            break
    return mid
print(search(0,len(nums)-1,nums,3)) 

这个程序使用二分查找算法在有序数组中查找目标值。二分查找算法的时间复杂度是O(logN)，相比于线性查找的O(N)更高效。

具体实现为：定义一个函数search，传入参数l、r、nums、target，其中l和r表示查找的左右边界，初始值为数组的首尾下标，nums表示目标数组，target表示查找的目标值。

在函数内部，首先使用while循环进行查找，直到找到目标值或者左右边界重合，循环结束。在循环中，定义mid作为当前左右边界的中间位置，然后判断nums[mid]和target的大小关系。

如果nums[mid]小于target，则说明目标值在mid的右侧，因此将左边界更新为mid+1；如果nums[mid]大于target，则说明目标值在mid的左侧，因此将右边界更新为mid-1；如果nums[mid]等于target，则说明已经找到目标值，直接跳出循环。

最后返回mid作为目标值在数组中的下标位置。

在程序中，调用search函数并传入参数0、len(nums)-1、nums、3，表示查找nums数组中值为3的元素的下标位置，并通过print语句输出结果。  

拓展训练

给定一个m*n的二维数组，其中每行的元素从左到右升序排序，

每列的元素从上到下升序排序，又给定一个目标值，请返回目标值是否存在于二维数组中。

程序设计

nums=[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
def search(nums,target):
    m=len(nums)
    n=len(nums[0])
    def helper(i,j):
        if i<0 or j>=n:
            return False
        if nums[i][j]==target:
            return True
        elif nums[i][j]<target:
            return helper(i,j+1)
        else:
            return helper(i-1,j)
    return helper(m-1,0)
print(search(nums,5)) 

程序分析 

题目要求我们在一个二维数组中查找目标值，且该矩阵有如下特点：

1. 每一行都是从左到右递增的；

2. 每一列都是从上到下递增的。

基于该特点，我们可以考虑从矩阵的右上角或者左下角开始搜索，这样每次可以排除一整行或一整列，使得时间复杂度为$O(m+n)$。

在本题中，我们选择从右上角开始搜索。具体思路如下：

1. 初始化矩阵的行列值，即$m$和$n$。

2. 指定右上角的元素作为起始点。

3. 从右上角开始进行搜索，若当前元素等于目标值，则返回True；

4. 若当前元素值小于目标值，则说明目标值可能在当前元素所在的行的右侧，因此将当前元素所在的行排除掉，继续向右搜索；

5. 若当前元素值大于目标值，则说明目标值可能在当前元素所在的列的上侧，因此将当前元素所在的列排除掉，继续向上搜索。

6. 若搜索到矩阵的边缘仍未找到目标值，则返回False。

按照上述思路，我们可以写出如下代码：

归并排序

程序设计

#归并排序
lst=list(map(int,input().split(' ')))
def MergeSort(num):
    if(len(num)<=1):
        return num
    mid=int(len(num)/2)
    llist,rlist=MergeSort(num[:mid]),MergeSort(num[mid:])
    result=[]
    i,j=0,0
    while i<len(llist) and j<len(rlist):
        if rlist[j]<llist[i]:
            result.append(rlist[j])
            j+=1
        else:
            result.append(llist[i])
            i+=1
    result+=llist[i:]+rlist[j:]
    return result
print(MergeSort(lst)) 

程序分析

归并排序是一种基于分治思想的排序算法，将一个序列分成两个子序列，每个子序列递归进行排序，最后将两个排好序的子序列合并起来。该算法的时间复杂度为O(nlogn)，稳定性强，适用于大规模数据排序，并且空间复杂度较小。

在算法实现过程中，我们需要先将原序列划分成左右两个子序列，然后递归地对这两个子序列进行排序，最后将排好序的子序列合并成一个有序序列。合并过程中，我们需要比较左右两个子序列的元素大小，将较小的元素添加到新的序列中，然后再将剩余的序列添加到新序列末尾即可。

归并排序的优点在于稳定性强、时间复杂度低，适用于处理大规模数据，但是需要额外的存储空间来存储合并后的序列。此外，归并排序也可以应用于外部排序，即硬盘超过内存容量的情况下对大规模数据进行排序。

总体来说，归并排序是一种非常实用的排序算法，应用广泛，值得学习和掌握。

总结

理解分治算法的原理，解决一些简单的问题。