Содержание

• Сравнительная таблица
• Определение линейного поиска
• Определение бинарного поиска
• Вывод

Линейный поиск и бинарный поиск - это два метода, которые используются в массивах для поиск элементы. Поиск - это процесс поиска элемента в списке элементов, сохраненных в любом порядке или случайным образом.

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

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

1. Сравнительная таблица
2. Определение
3. Ключевые отличия
4. Вывод

Сравнительная таблица

Основа для сравнения	Линейный поиск	Бинарный поиск
Сложность времени	НА)	O (журнал 2 N)
Лучшее время дела	Первый Элемент O (1)	Центральный элемент O (1)
Необходимое условие для массива	Не требуется	Массив должен быть в отсортированном порядке
Худший случай для N числа элементов	Требуется N сравнений	Можно сделать вывод только после входа2N сравнений
Может быть реализовано на	Массив и связанный список	Не может быть непосредственно реализовано в связанном списке
Вставить операцию	Легко вставляется в конец списка	Требуется обработка для вставки в нужном месте, чтобы поддерживать отсортированный список.
Тип алгоритма	Итеративный характер	Разделяй и властвуй в природе
Полезность	Прост в использовании и не требует каких-либо заказанных элементов.	В любом случае хитрый алгоритм и элементы должны быть организованы по порядку.
Строки кода	Меньше	Больше

Определение линейного поиска

При линейном поиске каждый элемент массива извлекается один за другим в логическом порядке и проверяется, является ли этот элемент нужным или нет. Поиск будет неудачным, если все элементы будут доступны, а нужный элемент не найден. В худшем случае, в среднем случае нам может понадобиться отсканировать половину размера массива (n / 2).

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

КПД линейного поиска

Потребление времени или количество сравнений, выполненных при поиске записи в таблице поиска, определяет эффективность метода. Если нужная запись присутствует в первой позиции таблицы поиска, выполняется только одно сравнение. Когда желаемая запись является последней, тогда нужно сделать n сравнений. Если запись должна присутствовать где-то в таблице поиска, в среднем количество сравнений будет (n + 1/2). Наихудший случай эффективности этого метода - O (n) обозначает порядок выполнения.

Программа C искать элемент с линейной техникой поиска.

#включают #включают void main () {int a, n, i, item, loc = -1; clrscr (); f (" nВведите номер элемента:"); scanf ("% d", & n); f («Введите цифры: n»); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nВведите номер для поиска:"); scanf ("% d", & item); for (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; перемена; }} if (loc> = 0) {f (" n% d находится в позиции% d:", item, loc + 1); } else {f (" n Элемент не существует"); } getch (); }

Определение бинарного поиска

Бинарный поиск - чрезвычайно эффективный алгоритм. Этот метод поиска занимает меньше времени при поиске данного элемента при минимально возможных сравнениях. Чтобы выполнить бинарный поиск, сначала мы должны отсортировать элементы массива.

Логика этой техники приведена ниже:

• Сначала найдите средний элемент массива.
• Средний элемент массива сравнивается с элементом для поиска.

Возможны три случая:

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

Повторите те же шаги, пока элемент не будет найден или исчерпан в области поиска. В этом алгоритме каждый раз область поиска уменьшается. Поэтому число сравнений не более log (N + 1). В результате это эффективный алгоритм по сравнению с линейным поиском, но массив должен быть отсортирован перед выполнением двоичного поиска.

Программа C найти элемент с помощью техники двоичного поиска.

#включают void main () {int i, beg, end, middle, n, search, array; f («Введите номер элемента n»); зсапЕ ( "% d", & п); f («Введите% d чисел n», n); для (i = 0; i <n; i ++) scanf ("% d", & array); f («Введите номер для поиска n»); scanf ("% d", & search); прошу = 0; end = n - 1; средний = (начало + конец) / 2; while (beg <= end) {if (array <search) beg = middle + 1; иначе if (array == search) {f ("Поиск выполнен успешно. n% d найден в местоположении% d. n", поиск, середина + 1); перемена; } else end = middle - 1; средний = (начало + конец) / 2; } if (beg> end) f ("Поиск не выполнен!% d отсутствует в списке. n", поиск); Геч (); }

1. Линейный поиск носит итеративный характер и использует последовательный подход. С другой стороны, бинарный поиск реализует подход «разделяй и властвуй».
2. Временная сложность линейного поиска составляет O (N), в то время как двоичный поиск имеет O (log₂N).
3. Наилучшее время в линейном поиске относится к первому элементу, то есть O (1). В отличие от бинарного поиска, это для среднего элемента, то есть O (1).
4. В линейном поиске наихудший случай для поиска элемента - это N чисел сравнения. Напротив, это журнал₂N номер сравнения для бинарного поиска.
5. Линейный поиск может быть реализован как в массиве, так и в связанном списке, тогда как бинарный поиск не может быть реализован непосредственно в связанном списке.
6. Как мы знаем, для бинарного поиска требуется отсортированный массив, что является причиной, по которой требуется обработка для вставки в нужное место для поддержания отсортированного списка. Напротив, линейный поиск не требует отсортированных элементов, поэтому элементы легко вставляются в конец списка.
7. Линейный поиск прост в использовании, и нет необходимости в каких-либо упорядоченных элементах. С другой стороны, алгоритм двоичного поиска, однако, сложен, и элементы обязательно располагаются по порядку.

Вывод

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

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