Основное различие между линейным поиском и бинарным поиском состоит в том, что бинарный поиск занимает меньше времени для поиска элемента из отсортированного списка элементов. Таким образом, можно сделать вывод, что эффективность метода двоичного поиска выше, чем линейный поиск.
Еще одно различие между ними заключается в том, что для бинарного поиска существует предварительное условие, то есть элементы должны быть отсортированы, тогда как в линейном поиске такого условия нет. Хотя оба метода поиска используют разные методы, которые обсуждаются ниже.
Сравнительная таблица
| Основа для сравнения | Линейный поиск | Бинарный поиск |
|---|---|---|
| Сложность времени | НА) | O (log 2 N) |
| Лучшее время дела | Первый Элемент O (1) | Центральный элемент O (1) |
| Необходимое условие для массива | Не требуется | Массив должен быть в отсортированном порядке |
| Худший случай для N числа элементов | Требуется N сравнений | Можно сделать вывод только после лога 2 N сравнений |
| Может быть реализовано на | Массив и связанный список | Не может быть непосредственно реализовано в связанном списке |
| Вставить операцию | Легко вставляется в конец списка | Требуется обработка для вставки в нужном месте, чтобы поддерживать отсортированный список. |
| Тип алгоритма | Итеративный характер | Разделяй и властвуй в природе |
| Полезность | Прост в использовании и не требует каких-либо заказанных элементов. | В любом случае хитрый алгоритм и элементы должны быть организованы по порядку. |
| Строки кода | Меньше | Больше |
Определение линейного поиска
При линейном поиске каждый элемент массива извлекается один за другим в логическом порядке и проверяется, является ли этот элемент нужным или нет. Поиск будет неудачным, если все элементы будут доступны, а нужный элемент не найден. В худшем случае, в среднем случае нам может понадобиться отсканировать половину размера массива (n / 2).
Поэтому линейный поиск может быть определен как метод, который последовательно проходит через массив для определения местоположения данного элемента. Приведенная ниже программа иллюстрирует поиск элемента массива с использованием поиска.
Эффективность линейного поиска
Потребление времени или количество сравнений, выполненных при поиске записи в таблице поиска, определяет эффективность метода. Если нужная запись присутствует в первой позиции таблицы поиска, выполняется только одно сравнение. Когда желаемая запись является последней, тогда нужно сделать n сравнений. Если запись должна присутствовать где-то в таблице поиска, в среднем количество сравнений будет (n + 1/2). Наихудший случай эффективности этого метода - O (n) обозначает порядок выполнения.
C Программа для поиска элемента с помощью линейного метода поиска.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nВведите номер элемента:"); scanf ("% d", & n); printf («Введите цифры: \ n»); for (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nВведите номер для поиска:"); scanf ("% d", & item); for (i = 0; i = 0) {printf ("\ n% d находится в позиции% d:", item, loc + 1); } else {printf ("\ n Элемент не существует"); } getch (); } Определение бинарного поиска
Бинарный поиск - чрезвычайно эффективный алгоритм. Этот метод поиска занимает меньше времени при поиске данного элемента при минимально возможных сравнениях. Чтобы выполнить бинарный поиск, сначала мы должны отсортировать элементы массива.
Логика этой техники приведена ниже:
- Сначала найдите средний элемент массива.
- Средний элемент массива сравнивается с элементом для поиска.
Возможны три случая:
- Если элемент является обязательным элементом, то поиск успешен.
- Если элемент меньше требуемого элемента, тогда ищите только первую половину массива.
- Если он больше, чем требуемый элемент, ищите во второй половине массива.
Повторите те же шаги, пока элемент не будет найден или исчерпан в области поиска. В этом алгоритме каждый раз область поиска уменьшается. Поэтому число сравнений не более log (N + 1). В результате это эффективный алгоритм по сравнению с линейным поиском, но массив должен быть отсортирован перед выполнением двоичного поиска.
C Программа для поиска элемента с помощью техники двоичного поиска.
#include void main () {int i, beg, end, middle, n, search, array [100]; printf («Введите номер элемента \ n»); зсапЕ ( "% d", & п); printf («Введите% d цифр \ n», n); для (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf («Введите номер для поиска \ n»); scanf ("% d", & search); прошу = 0; end = n - 1; средний = (начало + конец) / 2; while (beg <= end) {if (array [middle] end) printf ("Поиск не выполнен!% d отсутствует в списке. \ n", поиск); Геч (); } Ключевые различия между линейным и двоичным поиском
- Линейный поиск носит итеративный характер и использует последовательный подход. С другой стороны, бинарный поиск реализует подход «разделяй и властвуй».
- Временная сложность линейного поиска составляет O (N), в то время как двоичный поиск имеет O (log 2 N).
- Наилучшее время в линейном поиске - для первого элемента, т. Е. O (1). В отличие от бинарного поиска, это для среднего элемента, т. Е. O (1).
- В линейном поиске наихудший случай для поиска элемента - это N чисел сравнения. Напротив, это log 2 N числа сравнения для двоичного поиска.
- Линейный поиск может быть реализован как в массиве, так и в связанном списке, тогда как бинарный поиск не может быть реализован непосредственно в связанном списке.
- Как мы знаем, для бинарного поиска требуется отсортированный массив, что является причиной, по которой требуется обработка для вставки в нужное место для поддержания отсортированного списка. Напротив, линейный поиск не требует отсортированных элементов, поэтому элементы легко вставляются в конец списка.
- Линейный поиск прост в использовании, и нет необходимости в каких-либо упорядоченных элементах. С другой стороны, алгоритм двоичного поиска, однако, сложен, и элементы обязательно располагаются по порядку.
Заключение
В зависимости от приложения могут быть полезны как линейный, так и двоичный алгоритмы поиска. Если массив представляет собой структуру данных, а элементы расположены в отсортированном порядке, то для быстрого поиска предпочтительным является двоичный поиск. Если связанный список является структурой данных независимо от того, как элементы расположены, линейный поиск принимается из-за недоступности прямой реализации алгоритма двоичного поиска.
Типичный алгоритм двоичного поиска не может быть использован для связанного списка, потому что связанный список является динамическим по своей природе, и неизвестно, где фактически назначен средний элемент. Следовательно, существует потребность в разработке варианта алгоритма бинарного поиска, который может работать и в связанном списке, потому что бинарный поиск выполняется быстрее, чем линейный поиск.
