Finding the smallest number in array with O(log n)

Question

I had the sorted array that formulated by S[i] = (a*i)+b

But, I'm removing one element in the array, and my goal is to find which element had been removed (by check element in the array is 𝑆[𝑖] ≠ 𝑎𝑖 + 𝑏) by starting from index 0.

Example: define a=3 and b=1, the array should be 1,4,7,10,16,19,22 The answer should be 4 because S[4] should be 13 not 16 (the smallest number that missing is 13).

My idea is using Binary search is the answer to this question? because if we perform Binary search in the best case computation time should be O(log n)

Thank you for your answer.

Answer 1

A common misconception is - if you have a sorted array, you can apply binary search on it. It actually depends on the problem. Binary search requires a specific property to be met if you want to solve a problem with a binary search.

For your task, the binary search should look for the first element which doesn't satisfy the a x i + b equation.

Let's say, our binary search uses a function check_valid(i), it checks if S[i] == a x i + b or not. It returns true or false.

Now, to satisfy the conditions of binary search your input array must have the following structure when we run check_valid linearly (from 1 to n).

True, True, True, True, ..... False, False, False, False, False

(Look, for your case your array doesn't even need to be sorted, but it should follow the property that: for an index k, every element before k does satisfy the equation and every element after k does not) That means binary search is only applicable if all of the element after an index doesn't satisfy S[i] = a x i + b, otherwise you must have to run a linear search.

Another thing you should realize is that, there are n elements in the array, even taking the input is O(n), so no pre-processing can be applied to the array.

If your array doesn't have the property, there is no log(n) solution at all.