Take the middle element if it is a blip then return it
Otherwise,
- if the left element is greater than the middle element then there exist a blip in the left array
- or if the right element is greater then there exist a blip in the right array.
Example:
If $A$ is an array of size $n$ then the middle element of the array is the number $A[(n+1)/2]$ when $n$ is odd and the middle element of the array is $A[n/2]$ when $n$ is even.
Now, take the unsorted array $10,9,8,11,12,13,15,16,12$
Middle element in the array $→ 12$
- Left of middle $11$ (smaller)
- Right of middle $13$ (greater)
So, blip present in the right array $13,15,16,12$
Middle element of right array 15
- Right of middle $16$ (greater)
- Left of middle $13$ (smaller)
So, blip is present in the right array $16,12$
Middle $:16$
- Right of middle 12 (smaller)
So, $16$ is a blip.
This will hold for any unsorted array take more examples to verify it. The time complexity will be $O(\log n)$ as in each step we are reduing the problem size by at least half.