Envyless location using divide and conquer

Question

We have a cake of length $n$ and we have two arrays $A$ and $B$ of size $n$. The two arrays have order like below. $A[0]<A[1]<\dots <A[n]$, $B[0]>B[1]>\dots >B[n]$. We define a envyless location as a cut in the cake where it satisfies $A[i]=B[i]$. For example, $A=[1,2,3,4,5,6,7]$ and $B=[7,6,5,4,3,2,1]$, $A[3]=B[3]=4$, therefore, cutting the cake at length 4 makes the cut envyless. If the algorithm finds an envyless location it returns it's location, and if the envyless location does not exist, it returns null. I am trying to use divide and conquer to solve this problem with worst-case runtime of $O(\log n)$.

I have tried the following procedure and failed. First, divide the cake in half. Find the mid point of the splitted cake and compare $A[mid]$ and $B[mid]$. If found, terminate and return the location. If not found, keep on dividing and comparing.
I expected this to run on $O(\log n)$ time but it cannot because for example, if $A=[1,2,3,4,5,6]$ and $B=[20,11,9,8,7,6]$, the envyless location is at location 6, and the algorithm needs to do $n$ comparison, making the algorithm to run at $O(n\log n)$.

Any help will be very helpful.

Answer 1

If $A[\text{mid}] < B[\text{mid}]$ then you can recurse on $A[\text{mid}+1, \dots, n]$ and $B[\text{mid}+1, \dots,n]$ since, if an envyless cut exists, it must be after location $mid$.

The situation $A[\text{mid}] > B[\text{mid}]$ is symmetric and you can recurse on $A[0, \dots, \text{mid}-1]$ and $B[0, \dots, \text{mid}-1]$.

The resulting algorithm takes time $T(n) \le T(\lfloor n/2 \rfloor) + O(1)$, which has solution $T(n) = O(\log n)$.