Sort Algorith Design And Analysis

[jim_underpants]

Design and analyze an algorithm that searchs for an element x in a sorted table A(with n elements), so that its complexity is O(logD). D stands for distance, counting the amount of elements between the first element and the element x in table A. Simpler, D is the position of the element x in the sorted table A.

[firstPerson]

Hint, binary search

[jim_underpants]

yeah i tried binary, but that one with distance gets me confused. It's only pseudocode... but I think I have to put an upper limit or something like that, any suggestions?

[firstPerson]

hmm good question. Maybe if you split up the arrays into m-segments and possibly run it parallel. Interesting question.