Let's say we have an unsorted array with numbers from 0 to n (n = 2^k - 1, k is an integer) except one. My goal is to find the missing number.
I am aware of the XOR method or the sum method. However, I have to use divide and conquer strategy and something that has to do with the median number of the array.
My thought is to find the median of the array and then to divide the array into 2 arrays recursively. (One will have the numbers that are smaller than or equal to the median and the other those which are greater. Something like binary search).
However, I do not think that this works. What changes do you suggest?
You can divide the array into 2 arrays, one with values smaller, the other with values greater than your median. You can the check how many elements both of these arrays should have, based on the assumption of your first sentence.
One of the arrays then must be 1 smaller than it is supposed to be. Therefore you can search there.
Your exit condition would then be something like that the array should containg all elements between x and x (so just x), but it is empty. Therefore x is the missing element.