How to search an almost sorted array faster than O(n) time?
Let's say you have n = 100, $a_1 = 50$, $a_{100} = 100$, and $a_{50} = 73$. You would then know that the range from $a_1$ to $a_{50}$ contains all numbers from 50 to 73, and maybe some others, and the range $a_{50}$ to $a_{100}$ contains all numbers from 73 to 100, and maybe some others. 

I think binary search will actually work, if the number you are looking for is within the interval from the first to the last array element. You will always know one half which must contain the number you are looking for, and one half which might contain the number so obviously you search the half that must contain it. 

If the number is outside that range, you may have to check every single item: You could have $a_i = 0$ for every $i$ except $a_k = 1$. You can examine $n-1$ items $a_i$ which are all 0, and you still don't know if 1 is in the array or not; the one remaining element could be $-1$, $0$ or $+1$.