分治法递归检查数组升序的边界判断及基例逻辑疑问

问题1：a⌊n/2⌋−1 ≤ a⌊n/2⌋判断条件的设计逻辑 #

分治法校验数组升序的核心逻辑是把数组拆分为左右两个子段，分别校验两个子段内部是升序的，此时要保证整个数组升序，还需要补一个左右子段衔接处的合法性校验：左子段的最大值（也就是左子段最后一个元素）必须小于等于右子段的最小值（也就是右子段第一个元素）。
⌊n/2⌋是右子段的第一个下标，⌊n/2⌋-1是左子段的最后一个下标，这个条件就是用来校验衔接处的合法性，避免出现左右子段内部都升序，但衔接处逆序的问题（比如数组[1,3,2,4]拆分后左段[1,3]、右段[2,4]都符合升序，但整体不是升序）。 #

问题2：为什么不用a⌊n/2⌋ ≤ a⌊n/2⌋+1作为替代 #

这个判断没有绝对的对错，完全和你拆分区间的规则绑定：

• 如果你拆分规则是左段为[0, ⌊n/2⌋-1]、右段为[⌊n/2⌋, n-1]，就用a[⌊n/2⌋-1] ≤ a[⌊n/2⌋]
• 如果你拆分规则是左段为[0, ⌊n/2⌋]、右段为[⌊n/2⌋+1, n-1]，就用a[⌊n/2⌋] ≤ a[⌊n/2⌋+1]
  如果选错判断条件，要么会漏校验衔接点，要么会出现数组下标越界的问题。

问题3：基例从h<=l改为h<l触发栈溢出的原因 #

基例的作用是终止递归，h<=l表示当前区间长度为0或1，天然符合升序要求，不需要继续拆分直接返回True。
修改为h<l后，区间长度为1（h==l）的场景不会触发终止条件，会继续执行拆分逻辑。如果你的拆分规则是左子区间包含mid（比如co(a,l,mid)），此时mid=l，左递归的入参和当前递归完全一致，就会进入无限递归，最终导致栈溢出。 #

问题4：示例代码中为什么用a[mid] < a[mid+1]而不是a[mid-1] < a[mid] #

首先你的代码存在逻辑漏洞：你当前的拆分规则是把区间拆分为[l, mid-1]、mid、[mid+1, h]三部分，仅判断a[mid] < a[mid+1]只覆盖了mid和右子段的衔接校验，漏掉了左子段和mid的衔接校验a[mid-1] < a[mid]，比如测试数组[3,1,2]就会被误判为升序。
判断条件的选择和拆分规则强绑定：

• 如果你调整拆分规则为左段[l, mid]、右段[mid+1, h]，那么只需要校验a[mid] < a[mid+1]即可，因为a[mid-1] < a[mid]属于左段内部的校验，已经被递归逻辑覆盖，不需要重复判断
• 如果你坚持当前三部分拆分的规则，就需要同时添加两个衔接判断，还要加下标合法性的边界判断
  你贴的示例代码是试错出来的、未覆盖所有边界的版本，不建议直接使用。

相关参考示意图 #

相关示例代码 #

def co(a, l, h):
  if h <= l:
    return True
  mid = l + ((h-l)//2)
  cl = co(a, l, mid-1)
  rl = co(a, mid+1, h)
  return rl and cl and a[mid] < a[mid+1] 

#c = [3, 5, 7, 9, 11,12]
c = [3, 5]

print(co(c, 0, len(c) - 1))

内容的提问来源于stack exchange，提问作者Hax