ascending order check recursively

Question

What I try to do is to check a given array is ordered in an ascending manner by divide-and-conquer approach.

I wonder what the logic behind the additional return case (a⌊n/2⌋−1 ≤ a⌊n/2⌋) is to reach to the final result. I attempted to solve the problem without looking at its solution but I couldn't figure out how the author discovers/devises a⌊n/2⌋−1 ≤ a⌊n/2⌋ case. It is really hard for me to unearth the case.

Actually, Why not a⌊n/2⌋ ≤ a⌊n/2⌋+1 instead? And the base case case, why I'm stackoverflowed when I remove equality from the base case, that is h<l?

with trial and error approach, I tried to write the following.

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] 

    # how  is a[mid] < a[mid+1] devised ??
    # why not a[mid-1] < a[mid] ??

  

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


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

Answer 1

And the base case case, why I'm stackoverflowed when I remove equality from the base case, that is h<l?

Assume c=[3, 5]. If you replace h<=l with h<l, then when you compute co(a, 1, 1), then mid = 1+0 ... then rl = co (a, 1+1, 1) and a[2] gives you stackoverflow.

How is a[mid] <= a[mid+1] devised ??

• You need to compare the most-right element of subproblem1 with the most-left element of subproblem2. The order of these two elements are not taken into account in subproblem1 and subproblem2.

• Be careful with Python indexing. 1) When you split the list into a[l:mid-1] and a[mid+1,h], you leave out a[mid-1] and a[mid]. 2) When you write co(c, 0, len(c) - 1) you leave out the last element of c (see Comment4).

There are some mistakes in your code, see my comments.

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] ### Comment1: this misses checking a[mid-1] <= a[mid]

    # how  is a[mid] < a[mid+1] devised ??  ### Comment2: you should use <= rather than <
    # why not a[mid-1] < a[mid] ??
 

#c = [12, 3, 5, 7, 9, 11,12]  ### Comment3: your code returns True for this unordered list!
#c = [3, 5, 7, 9, 11,12]
c = [3, 5]


print(co(c, 0, len(c) - 1))  ### Comment4: len(c)-1 should be len(c) otherwise it's not the whole list

Below, I fixed the list indexing in your code. Note that the test becomes h <= l+1 because in Python the list a[mid:mid+1] contains one element.

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