# How to search an almost sorted array faster than O(n) time?

Assume a 1-indexed array A[1...n], containing integers, where A[1] ≤ A[n]. The contents of the array have the following property : for 1 ≤ i < n, |A[i] − A[i + 1]| ≤ 1.

Develop an efficient recursive algorithm to find j such that A[j] = z, where A[1] ≤ z ≤ A[n]. The algorithm must be more efficient that O(n).

Binary search was my first thought but you would still have to search through both halves because it doesn't have to be from low to high.

• The first guess would be along the lines of binary search. Have you tried pursuing that direction? Jul 26 '19 at 17:55
• That was my first thought too but you would still have to search through both halves because it doesn't have to be from low to high. @YuvalFilmus Jul 26 '19 at 18:05
• Have you used the given? It implies that values cannot be “skipped”. Jul 26 '19 at 18:05
• You should also use the property that z lies between the first and last element (otherwise the task does require linear time). Jul 26 '19 at 18:51
• The title "almost sorted" is misleading since the array can be, for example, 1 2 3 4 3 2 1 2 3 4. The most descriptive adjective could be "no-skipping integer". Jul 26 '19 at 22:47

## 1 Answer

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$$.

• +1. An additional example when $a_{50}$ is not between $a_1$ and $a_{100}$ may make the answer more convincing. Jul 26 '19 at 22:56