Рубрики

Бинарный поиск в стандартной библиотеке шаблонов C ++ (STL)

Бинарный поиск — это широко используемый алгоритм поиска, который требует сортировки массива перед применением поиска. Основная идея этого алгоритма состоит в том, чтобы продолжать делить массив пополам (разделяй и властвуй) до тех пор, пока элемент не будет найден или все элементы не будут исчерпаны.

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

Прототип для бинарного поиска:

binary_search(startaddress, endaddress, valuetofind)

startaddress: the address of the first element of the array.
endaddress: the address of the last element of the array.
valuetofind: the target value which we have to search for.

// Программа CPP для реализации
// Двоичный поиск в
// Стандартная библиотека шаблонов (STL)
#include <algorithm>
#include <iostream>

  

using namespace std;

  

void show(int a[], int arraysize)

{

    for (int i = 0; i < arraysize; ++i)

        cout << a[i] << " ";

}

  

int main()

{

    int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };

    int asize = sizeof(a) / sizeof(a[0]);

    cout << "\n The array is : ";

    show(a, asize);

  

    cout << "\n\nLet's say we want to search for 2 in the array";

    cout << "\n So, we first sort the array";

    sort(a, a + asize);

    cout << "\n\n The array after sorting is : ";

    show(a, asize);

    cout << "\n\nNow, we do the binary search";

    if (binary_search(a, a + 10, 2))

        cout << "\nElement found in the array";

    else

        cout << "\nElement not found in the array";

  

    cout << "\n\nNow, say we want to search for 10";

    if (binary_search(a, a + 10, 10))

        cout << "\nElement found in the array";

    else

        cout << "\nElement not found in the array";

  

    return 0;

}

Вывод вышеуказанной программы:

The array is : 1 5 8 9 0 6 7 3 4 2 0

Let's say we want to search for 2 in the array
 So, we first sort the array

The array after sorting is : 0 1 2 3 4 5 6 7 8 9

Now, we do the binary search
Element found in the array

Now, say we want to search for 10
Element not found in the array

Связанная статья: std :: bsearch в C ++
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Бинарный поиск в стандартной библиотеке шаблонов C ++ (STL)

0.00 (0%) 0 votes