-基本思想
将一个规模为n的问题分解成k个规模较小的子问题。这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解
一、二分搜索算法
问题描述：在给定好的以排好序的n个元素的数组 l 中，查找出某一特定的值x
1.算法思想（T（n）=O（1）~O（log2n））
-将数组二分为两个，比较x和切分点 l[n//2] 的数值的大小
-若x较大，则在较大的数组中递归查找
-若x较小，则在较小的数组中递归查找
2.算法实现
def BinarySearch(lis, x, l, r):
if l <= r:
mid = (l+r)//2
if x == lis[mid]:
return mid
if x < lis[mid]:
return BinarySearch(lis, x, l, mid-1)
if x > lis[mid]:
return BinarySearch(lis, x, mid+1, r)
else:
return -1
*二、棋盘覆盖算法
问题描述：在一个2^k*2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。特殊方格在棋盘中可能出现的位置有4^k种。4种不同形状的L型骨牌（如下图）覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
1.算法思想（T（k）=O（4^k））
（1）先将棋盘划分为4部分。必定分为一个特殊棋盘和三个正常子棋盘
（2）若某子棋盘是特殊棋盘，那么递归的将子棋盘填充；若不是特殊棋盘，那么需要添加一个填充点（左上子棋盘的填充点是右下角；右上子棋盘的填充点在左下角；左下子棋盘的填充点在右上角；右下子棋盘的填充点在左上角）
（3）按照每2*2必有一个特殊方格的原则，将子棋盘继续4等分，所有子棋盘大小均为2*2。最后用骨牌填充
*2.算法实现
size = 8
res = [[0]*size for _ in range(size)]
num = 0
chessboard(size,1,1,0,0)
# size：当前棋盘的大小，x，y ：特殊方格的坐标，x 0 ，y0 ：当前棋盘的左上角坐标
def chessboard(size, x, y, x0, y0):
global res
global num
if size == 1: # 如果边的长度为1，返回执行下一条判断的语句
return
size //= 2
num += 1
mark = num
# 左上棋盘
if x < x0 + size and y < y0 + size:
chessboard(size, x, y, x0, y0)
else:
res[x0 + size - 1][y0 + size - 1] = mark # 覆盖右下角
chessboard(size, x0 + size - 1, y0 + size - 1, x0, y0) # 不能是return chessboard的形式，因为执行到return语句就不会继续向下执行判断了
# 右上棋盘
if x < x0 + size and y >= y0 + size:
chessboard(size, x , y, x0, y0 + size)
else:
res[x0 + size - 1][y0 + size] = mark # 覆盖左下角
chessboard(size, x0 + size - 1, y0 + size, x0, y0 + size)
# 左下棋盘
if x >= x0 + size and y < y0 + size:
chessboard(size, x, y, x0 + size, y0)
else:
res[x0 + size][y0 + size - 1] = mark # 覆盖右下角
chessboard(size, x0 + size, y0 + size - 1, x0 + size, y0)
# 右下棋盘
if x >= x0 + size and y>= y0 + size:
chessboard(size, x, y, x0 + size, y0 + size)
else:
res[x0 + size][y0 + size] = mark # 覆盖左上角
chessboard(size, x0 + size, y0 + size, x0 + size,y0 + size)
分治（一）二分搜索和棋盘覆盖
原文：https://www.cnblogs.com/xiaoqichaoren/p/12951644.html
