Этот вид поиска применим только к отсортированным массивам. Его идея заключается в том, что сначала выбирается элемент в середине массива. Поскольку массив отсортирован, то если искомый элемент больше выбранного, то поиск далее продолжается только в правой части массива. Соответственно, если искомый элемент меньше, просматривается только левая половина массива. Ну если средний элемент является искомым, то…

Читать далее

Разновидностью линейного поиска является поиск с барьером, который заключается в том, что в конец исследуемого массива добавляется искомый элемент. Выигрыша в сложности алгоритма этот метод не дает, она также составляет O(N). Он позволяет избавиться от условия проверки достижения искомого элемента в цикле. Однако недостаток метода заключается в необходимости увеличивать пазмер массива на один элемент. Это…

Читать далее

Этот вид поиска является самым простым и заключается в последовательном просмотре элементов массива, пока не будет найден искомый элемент. В случае отсутствия искомого элемента метод возвращает некоторое фиксированное значение, например, -1 или false. В худшем случае придется просмотреть все элементы массива, таким образом, его асимптотическая сложность составляет O(N). Далее представлен алгоритм линейного поиска на разных…

Читать далее