Say we are given sorted list S with n items i.e. n entries of the form (key,value) whose keys are strictly increasing with indexing Consider a "scrambled" version of it S' in which elements may have been moved by at most two locations: that is, elements previously in index i may be indexed within range [i-2, i+2].
Provide a searching algorithm that still provides the functionality of the searching algorithm with runtime O(log n). Provide proof for the correctness and the runtime.