Линейный поиск и бинарный поиск
Содержание
- Содержание: Разница между линейным поиском и бинарным поиском
- Сравнительная таблица
- Бинарный поиск
- Ключевые отличия
- Заключение
- Пояснительное видео
Разница между линейным поиском и бинарным поиском заключается в том, что при линейном поиске каждый элемент проверяется и сравнивается, а затем сортируется, тогда как при бинарном поиске список, который должен быть отсортирован, делится на две части и затем сортируется. Поиск и сортировка являются двумя основными понятиями в компьютерном программировании. Многие алгоритмы используются для поиска и сортировки, но два наиболее часто используемых алгоритма для поиска и сортировки - это линейный поиск и двоичный поиск.
Разница между линейным поиском и двоичным поиском заключается в работе и эффективности обоих алгоритмов. Бинарный поиск является гораздо более эффективным алгоритмом по сравнению с алгоритмом линейного поиска. Итерация или время, необходимое для сравнения каждого значения перед сортировкой, меньше в бинарном поиске по сравнению с линейным поиском.
Линейный поиск - очень сложный алгоритм, если вы хотите искать число в списке, сравнивать и иногда повторять количество значений в списке. Один за другим каждый элемент списка извлекается и сравнивается со смежным элементом. Все элементы доступны и проверяются, а затем правильный элемент найден. Наихудший случай может быть, если последнее число в списке - это число, которое нужно искать. Линейный поиск - это метод, с помощью которого выполняется поиск в массиве и поиск элемента для поиска. Если говорить об эффективности, то эффективность - это количество раз, которое программа должна запустить, чтобы найти это число. Если мы найдем искомое число в первой позиции, тогда нужно будет сделать только одно сравнение, и все будет отсортировано, но если нет, то сравнения придется делать снова и снова, и память тратится впустую. В среднем количество сравнений будет (n + 1/2). И в худшем случае эффективность этого метода O (n) обозначает порядок выполнения.
По сравнению с линейным поиском бинарный поиск очень эффективен. В этом методе массив делится на две части, и таким образом количество сравнений намного меньше по сравнению с бинарным поиском. Время также меньше в бинарном поиске по сравнению с линейным поиском. Бинарный поиск работает так, чтобы найти средний элемент массива, а затем средний элемент сравнивается с одной частью массива. Возможны три варианта: среднее число может быть числом, которое нам нужно найти, или числом, которое меньше среднего числа, или числом, которое больше середины среднего числа. Количество сравнений не более log (N + 1). Бинарный поиск по сравнению с линейным поиском является эффективным алгоритмом по сравнению с линейным поиском, но массив должен быть отсортирован перед выполнением бинарного поиска.
Содержание: Разница между линейным поиском и бинарным поиском
- Сравнительная таблица
- Бинарный поиск
- Ключевые отличия
- Заключение
- Пояснительное видео
Сравнительная таблица
| основа | Линейный поиск | Бинарный поиск |
| Смысл | Линейный поиск каждого элемента проверяется и сравнивается, а затем сортируется | Двоичный поиск в списке, который должен быть отсортирован, делится на две части, а затем сортируется.
|
| Сложность времени | Временная сложность линейного поиска составляет O (N). | Временная сложность двоичного поиска составляет O (log 2 N) |
| Тип алгоритма | Линейный поиск является итеративным. | Двоичный поиск - Разделяй и властвуй. |
| Строка кода | В линейном поиске нам нужно написать больше кода. | В бинарном поиске нам нужно писать меньше кода. |
Линейный поиск
Линейный поиск - очень сложный алгоритм, если вы хотите искать число в списке, сравнивать и повторять несколько раз количество значений в списке. Один за другим каждый элемент списка извлекается и сравнивается со смежным элементом. Доступ ко всем элементам и проверка, а затем правильный элемент найден. Наихудший случай может быть, если последнее число в списке - это число, которое нужно искать. Линейный поиск - это метод, с помощью которого выполняется поиск в массиве и поиск элемента для поиска. Если говорить об эффективности, то эффективность - это количество раз, которое программа должна запустить, чтобы найти это число. Если мы найдем искомое число в первой позиции, тогда нужно будет сделать только одно сравнение, и все будет отсортировано, но если нет, то сравнения придется делать снова и снова, и память тратится впустую. В среднем количество сравнений будет (n + 1/2). И в худшем случае эффективность этого метода O (n) обозначает порядок выполнения.
Бинарный поиск
По сравнению с линейным поиском бинарный поиск очень эффективен. В этом методе массив делится на две части, и таким образом количество сравнений намного меньше по сравнению с бинарным поиском. Время также меньше в бинарном поиске по сравнению с линейным поиском. Бинарный поиск работает так, чтобы найти средний элемент массива, а затем средний элемент сравнивается с одной частью массива.
Возможны три варианта: среднее число может быть числом, которое нам нужно найти, или числом, которое меньше среднего числа, или числом, которое больше середины среднего числа. Количество сравнений не более log (N + 1). Бинарный поиск по сравнению с линейным поиском является эффективным алгоритмом по сравнению с линейным поиском, но массив должен быть отсортирован перед выполнением бинарного поиска.
Ключевые отличия
- При линейном поиске каждый элемент проверяется и сравнивается, а затем сортируется, тогда как бинарный поиск по списку, который должен быть отсортирован, делится на две части и затем сортируется.
- Временная сложность линейного поиска составляет 0 (N), тогда как временная сложность бинарного поиска составляет O (log2N).
- Линейный поиск является итеративным, тогда как бинарный поиск - «Разделяй и властвуй».
- В линейном поиске нам нужно написать больше кода, тогда как в бинарном поиске нам нужно написать меньше кода.
Заключение
В этой статье выше мы видим четкую разницу между линейным поиском и бинарным поиском.
