Если видео недоступно для просмотра, попробуйте выключить блокировщик рекламы.

Наконец перейдем к реальным алгоритмам, для начала рассмотрим один их самых простых – поиск элемента в отсортированном массиве, именно его реализация дает представление о том, как может быть полезна О нотация. Это самая базовая алгоритмическая задача, которую нередко спрашивают на собеседованиях. С одной стороны, для подобных алгоритмов используют уже готовые функции стандартной библиотеки, с другой – подобные вопросы на собеседованиях позволяют узнать полезное о кандидате:

  • Насколько вы вообще в курсе о существовании алгоритмов.
  • Способны ли вы программировать.
  • Как работает ваше алгоритмическое мышление.

Наивный подход будет выглядеть как перебор элементов в массиве до встречи с нужным, тогда если количество элементов равно n и нужный нам элемент будет последним, нам потребуется сделать n проверок элементов до нахождения нужного, про такой случай и говорят что сложность алгоритма равна O(n).

Рассмотрим другой подход – возьмем средний элемент отсортированного массива и сравним его c искомым. Если элемент меньше – продолжим поиск в левой части массива, если больше в правой, пока не останется нужный элемент. Таким образом нам понадобится число операций равное тому, сколько раз нам нужно поделить массив размером n пополам. Например для массива в 16 элементов мы сначала поделим его на два по 8, потом 8 на два по 4, потом 4 на два по 2 и на конец 2 пополам, те всего 4 операции в худшем случае. Такое число равно двоичному логарифму: число можно столько раз разделить на 2, сколько нужно умножать 2 на 2(возводить в степень) чтобы получить это число.

16 = 24.

А логарифм это функция обратная возведению в степень, показывающая сколько же раз нужно умножать 2(возводить в степень), чтобы получить 16.

log2 16 = 4.

Код алгоритма будет выглядеть следующим образом:

public int binarySearch(int[] sortedArray, int key, int low, int high) {
    int index = -1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (sortedArray[mid] < key) {
            low = mid + 1;
        } else if (sortedArray[mid] > key) {
            high = mid - 1;
        } else if (sortedArray[mid] == key) {
            index = mid;
            break;
        }
    }
    return index;
}

А использовать данную функцию можно следующим образом:

int first = 0; //первый элемент массива
int last = sortedArray.length - 1; //последний элемент массива

binarySearch(sortedArray, 42, first, last);

Вот и все, теперь вы алгоритмист.

Мы учим программированию с нуля до стажировки и работы. Попробуйте наш бесплатный курс «Введение в программирование» или полные программы обучения по Node, PHP, Python и Java.

Хекслет

Подробнее о том, почему наше обучение работает →