Бинарный поиск

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

Суть двоичного поиска заключается в нахождении позиции элемента в отсортированном массиве. Бинарный поиск решает проблему с помощью подхода «разделяй и властвуй». Это означает, что он делит проблему на наименьшие возможности для получения ответа. Первым шагом будет создание массива для поиска.

Попробуем найти значение 4. Нам потребуется установить 2 указателя. Один указатель будет называться low и размещаться на самой низкой позиции, а другой — high и будет предназначен для самой высокой позиции.

Нам также нужно найти средний элемент в нашем массиве. Мы можем создать переменную mid и приравнять ее к суммам самого низкого и самого высокого индексов, затем разделить сумму на 2. Это даст нам среднюю позицию массива: arr[(low + high)/2] = 6.

Теперь нам нужно проверить, равно ли искомое значение середине, меньше середины или больше середины. Если оно равно середине, то мы возвращаем mid. Если искомое значение больше, то мы заменяем low на low = mid + 1. Это означает, что мы ориентируемся на индексы массива после индекса mid. Если значение меньше середины, то мы заменяем high на high = mid + 1, где мы фокусируемся на элементах перед средней позицией.

Мы будем повторять эти шаги до тех пор, пока low не встретится с high или пока не будет найдено наше значение

GREATTTTT!!!!!! найдено 4

Псевдокод:

do until the pointers low and high meet each other.
    mid = (low + high)/2
    if (x == arr[mid])
        return mid
    else if (x > arr[mid]) // x is on the right side
        low = mid + 1
    else                       // x is on the left side
        high = mid - 1
Вход в полноэкранный режим Выход из полноэкранного режима

Код на JavaScript:

// Program to implement iterative Binary Search


// A iterative binary search function. It returns
// location of x in given array arr[low..high] is present,
// otherwise false

 function binarySearch(arr, x)
{   
    let low = 0;
    let high = arr.length - 1;
    let mid;
    while (high <= low) {
         mid = Math.floor((high - low) / 2);

        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            high = mid - 1;

        // Else the element can only be present
        // in right subarray
        else
            low = mid + 1;
    }

    // We reach here when element is not
    // present in array
    return false;
}
Вход в полноэкранный режим Выход из полноэкранного режима

Оцените статью
Procodings.ru
Добавить комментарий