One inversion

Exercise 2.12

Describe an algorithm of cost \Theta(\log n) that, given an element x and a table T[1\dots n] with a single inversion determines whether x is in T or not.

First show that if a table has a single inversion, then the two elements of this inversion appear next to each other; that is, if (i, j) is the unique inversion in the table, then i + 1 = j. Then use this fact to construct the algorithm required.

Recall that an inversion in a table A[1 \dots n] is a pair of indices that point to elements in inverted order; that is, a pair (i, j) such that 1 \leq i < j \leq n and A[i] > A[j].

Extra

Will your algorithm work if there were 2 inversions? Yes? No? Why?

After doing this exercise, you might want to solve the Jutge problem P33412 Resistant dichotomic search