Обьясните пожалуйста, чем так примечателен алгоритм бинарного поиска, и почему его так необходимо знать?
"Выполняется на упорядоченном одномерном массиве. Производит самый быстрый поиск при таких условиях. Максимальное количество сравнений(проходов) log2n.
Работает следующим образом: смотрим середину первоначального интервала - больше, меньше, равна ли искомому значению? Если равна - понятно что делаем, если меньше, то делаем новый интервал, который начинается с середины предыдущего интервала и заканчивается той же верхней границей предыдущего, т.е. это как-бы вторая половина исходного интервала, далее вся процедура повторяется. Если середина - больше искомого значения, то новый интервал будет первой половиной исходного интервала. И так итеративно сужаем наш интервал до тех пор, пока искомый элемент не будет найден или не дойдем до пустого интервала." - из источника.
Проще говоря, например, имея 1000 элементов, вы делите весь массив пополам. Ваше число больше или меньше чем 500? Если больше - проводите то же самое, только с правой частью массива, если меньше - с левой, и так рекурсивно до тех пор пока не найдёте нужный элемент. Этот поиск примечателен тем, что работает ооочень эффективно при больших размерах массива. Единственное что - массив должен быть отсортирован.