Input: SORTED array, target

Output: element_index or -1 if is not present in array

Complexity:

Avg: $O(\log{\log{n}})$

Worst: $O(n)$

Algorithm:

Идея заключается в том, что на основании максимального (самого правого) и минимального (самого левого) элементов мы делаем предположение о том, где находится target. Тут мы надеемся на то, что элементы расположены с примерно одним шагом.

В алгоритме ниже, скорее всего, проблема в формуле расчета позиции (guess), это надо будет ещё поправить.

<aside> ⚙️ left = 0; right = n-1;

$guess = arithmeticRounding(left + \frac{target - a_{left}}{a_{right} - a_{left}} * (a_{right} - a_{left}))$

$a_{guess}$ == target → print(guess); exit();

$a_{guess}$ < target → {

left = guess;

$guess = arithmeticRounding(left + \frac{target - a_{left}}{a_{right} - a_{left}} * (a_{right} - a_{left}))$

$a_{guess}$ == target → print(guess); exit();

$a_{guess}$ < target → {

left = guess;

…

};

};

$a_{guess}$ > target → {

right = guess;

$guess = arithmeticRounding(left + \frac{target - a_{left}}{a_{right} - a_{left}} * (a_{right} - a_{left}))$

$a_{guess}$ == target → print(guess); exit();

$a_{guess}$ < target → {

left = guess;

…

};

};

</aside>