рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Binary поиск

Реферат Курсовая Конспект

Выберите учебное заведение

Binary поиск

Binary поиск - раздел Образование, Unit 4. Sorting, Searching, and Complexity · 4.1 Sorting and Searching · 4.2 Complexity Assessments · Multiple-Choice Quiz Binary Поиск Считается Быстрым Алгоритмом Поиска, Подходит Для Наборов Данных...

Binary поиск считается быстрым алгоритмом поиска, подходит для наборов данных любого разумного размера. В отличие от линейного поиска, может использоваться даже для очень больших наборов данных, потому что исключает большое количество сравнений. Binary поиск отличается от линейного поиска тем, что в нем требуется, чтобы данные были обязательно сортированы.

Рассмотрим пример, как он искал бы элемент в следующем векторе.

Рисунок 1 Вектор, содержащий девять элементов

Найти элемент, который содержит значение 9. Все двоичные поиски начинаются, с исследования элемента находящегося строго по середине набора данных. В этом примере этот элемент содержит цифру 21.

Рисунок 2 Выбор среднего элемента

Значение, которое мы ищем, 9. Так как 9 меньше чем 21, мы знаем он должен быть сохранен слева от среднего элемента. Поэтому мы можем безопасно проигнорировать правую половину вектора и продолжить поиск рассматривая левую половину вектора. Рисунок 3 демонстрирует это разделение вектора.

Рисунок 2 Разделение вектора

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

Рисунок 4 Разделение вектора, снова

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

Size of vector	Max comparisons


1,000
10,000
100,000
1,000,000
10,000,000
100,000,000
1,000,000,000

Таблица 1 Максимальные сравнения двоичного поиска

Даже для вектора, который содержит миллиард элементов, алгоритм двоичного поиска должен сделать самое большее тридцать сравнений, чтобы найти любой элемент. Реализация алгоритма двоичного поиска приведена в Листинге 2.

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26:

// Finding an element in a vector using binary search template <typename T> int binary_search(const vector<T>& v, const T& item) { int low = 0; int high = v.size() - 1; int mid; while (low <= high) { // find the midpoint mid = (low + high) / 2; if (v[mid] < item) { low = mid + 1; // look in upper portion } else if (v[mid] > item) { high = mid - 1; // look in lower portion } else { return mid; // found it! } } return -1; // item not found }

Listing 2Finding an element in a vector using a binary search

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

Вместо того, чтобы положиться на их собственные реализации двоичного поиска, программисты на C++ могут использовать функцию STL binary_search. Интерфейс STL binary_search напоминает интерфейс функции find. Единственной разницей является то что функция binary_search возвращает bool значение, указывающее на успешность поиска. Использование в качестве примера STL binary_search приведено в wordsearch.cpp. Программа хранит слова, содержащиеся в текстовом файле. Пользователь вводит искомое слово и программа выполняет двоичный поиск, и находит это слово. Этот текст можно скачать здесь.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Unit 4. Sorting, Searching, and Complexity · 4.1 Sorting and Searching · 4.2 Complexity Assessments · Multiple-Choice Quiz

На сайте allrefs.net читайте: "Unit 4. Sorting, Searching, and Complexity · 4.1 Sorting and Searching · 4.2 Complexity Assessments · Multiple-Choice Quiz"

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Binary поиск

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Binary Search
A binary search is a fast search algorithm suitable for data sets of any reasonable size encountered. Unlike a linear search, it is suitable even for very large data sets because it eliminates larg

Sorting Overview
Many different basic sorting algorithms exist. Each of these algorithms has unique characteristics, behaviors, and requirements. For example, for the same set of data, one algorithm may perform far

Selection Sort
Selection sort is a basic sorting algorithm that works by making iterations, or passes, through the data being sorted. Each pass results in the placement of one element into its correct location. A

Краткий обзор
Существуют много различных алгоритмов сортировки. У каждого из этих алгоритмов есть уникальные характеристики, поведения, и требования. Например, для одной и той же задачи, один алгоритм может выпо

Selection Sort (Вид выбора)
Алгоритм selection sort является основным алгоритмом сортировки, который работает посредством итерации, или передачи сортируемых данных. Каждая передача приводит к перемещению одного элемента в его

Алгоритм
Quicksort является быстрым алгоритмом сортировки, который решает задачу используя проблему divide-and-conquer (разделяй и властвуй). Quicksort это рекурсия приводит массив элементов к элементарному

Реализация
Код quicksort реализации приведен в листинге 1. Эта quicksort реализация использует основную стратегию выбора центра как выбор среднего элемента. Это простой подход к реализации, и иногда он может

Использование функции сортировки STL
Стандартная библиотека шаблонов включает функции, которые программисты могут использовать, чтобы сортировать массивы контейнеров. Одна из этих функций sort функция. Функция sort выполняет быстрый s

Краткий обзор Хэш-таблиц
Хэш-таблица это структура данных ассоциативного массива, которая поддерживает очень быструю вставку элементов, удаление, и извлечение. Т.е. она позволяет хранить пары (ключ, значение) и выпо

Хеш-функции
Операции использующие хэш-таблицы эффективны, потому что позиция хранимой суммы может быть вычислена, используя ключ. Хэш-таблицы обычно реализуются как массив значений, а хеш-функция исполь

Реализация Хэш-таблицы
Следующий файл заголовочного файла и реализации объявляет и определяет шаблонный класс сопоставления хеша. Класс берет четыре шаблонных параметра. Первым является ключевой тип, и вторым является ти

The Algorithm
Quicksort is a fast sorting algorithm that uses a divide-and-conquer problem solving approach. Unlike the basic sorting algorithms we have already examined, quicksort uses recursion. Given an array

An Implementation
A quicksort implementation appears in Listing 1. This quicksort implementation uses a basic pivot selection strategy of selecting the middle element. This is a simple approach to implement, but one

Using the STL Sorting Functions
The Standard Template Library includes functions that programmers can use to sort a variety of containers. One of these functions is the sort function. The sort function performs a fast sort (typic

Overview of Hash Tables
A hash table is a data structure that supports very fast element insertion, removal, and retrieval. A hash table that is properly configured for the elements it contains can support these op

Hash Functions
Operations using hash tables are efficient because the position of a stored value can be calculated using the key. Hash tables are implemented typically as an array of values. A hash function

A Hash Table Implementation
The following header file and implementation file declares and defines a template hash map class. The class takes four template parameters. The first is the key type and the second is the value typ