Spotting the difference between two arrays using divide-and-conquer

Question

Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.

For simplicity, assume we can use two subroutines that can sum any subarray in our first and second arrays, respectively.

How would we use this to find a suitable algorithm using a divide-and-conquer approach? And if so, how many times would it have to call the subroutines? I assume we can start by dividing our arrays into two and solving our problem recursively from there.

Answer 1

Compute sums for the first two halves of the arrays, if they agree, the difference (if any) is in the second halves. If they don't agree, check first quarters, and so on.

Answer 2

You could just compare the values in a loop, which is trivial and works just fine. And we are now arguing about constant factors.

Consider how many array elements you read if the first two items are different (answer: n items from each array). Quite inefficient.

As a micro-optimisation adding k elements and comparing the sum would often be faster than comparing k elements. You could in a loop compare sums of k elements for some small fixed k.

Of course this only works if your guarantee (“exactly one item different”) is true, and the items are small integers so there is no overflow or rounding error. So just go with a straightforward loop unless speed is essential.