Мы живем в реальном практическом мире. Здесь некоторые люди благочестивы, а некоторые похожи на монстров. Итак, мы ищем в базе данных мира благочестивых людей. Мы не знаем, есть он в списке или нет, но нам нужно искать. Если он там, мы должны определить местонахождение. Итак, сначала мы реализуем простой способ, т.е. Линейный поиск.

Это простой подход, потому что нам просто нужно перебрать массив элементов и вернуть совпадение. Ура💃😎!!

Легкий, легкий, лимонный сок… Здесь мы вернем позицию первого благочестивого в массиве, т.е. 0.

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

Но говорят, что срезать путь нельзя🤪. Вот они верные. Линейный поиск идет с компромиссом. Здесь нам нужно перебрать массив, чтобы найти конкретный элемент. Таким образом, его производительность зависит от размера данных (размера массива). Если массив небольшой, мы можем использовать линейный поиск, но если размер массива большой (в нашем случае😀 т. е. массив типов людей по всему миру), не стоит вообще реализовывать линейный поиск, так как он сканирует один элемент за раз. время, не переходя ни к одному пункту. Таким образом, если в массиве 4 элемента, линейный поиск будет проходить через эти 4 элемента, если в массиве n элементов, линейный поиск будет проходить через все эти n элементов. Таким образом, его сложность равна 0(n). Это займет время в соответствии с количеством элементов в массиве.

Но они также сказали, что у каждой проблемы есть решение. Гьяни!!😜

Итак, вот наше решение: - Бинарный поиск. Да!! это там. Бинарный поиск решает проблему, которую создал линейный поиск, т.е. сложность 0(n).

Двоичный поиск снижает сложность поиска вдвое, как только вы найдете середину отсортированного списка. Это означает, что это займет половину времени, которое занял линейный поиск. Если линейный поиск занял n, то он займет n/2, или мы можем сказать log(n).

Вот посмотрим как.

Ох! код выглядит более длинным, чем линейный поиск. Но, как говорится, ничего стоящего не дается легко😀. гьян переполнен😀😀.

Здесь мы делим массив на две части. Итак, если длина массива равна n. Мы делим массив на две части размером n/2. И мы будем сравнивать только одну часть на основе средних элементов. Внутри цикла while мы получаем индекс среднего элемента и сравниваем средний элемент с нашей целью. Если мы найдем это значение в самой средней позиции, мы вернем эту позицию. Таким образом, здесь сложность алгоритма будет равна 0 (1). Нам вообще не нужно было обходить массив, и мы нашли целевое значение в средней позиции.

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

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

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

Знаешь?😀 Они сказали, что нет ничего идеального.😀 О боже!! ты, должно быть, уже раздражен😀. Двоичный поиск также имеет компромисс. В бинарном поиске массив должен быть отсортирован.

Так что выбирайте алгоритм поиска с умом. Если размер массива большой и отсортированный, очевидно, мы должны использовать бинарный поиск, потому что его сложность равна 0 (log n), в противном случае, если размер массива мал или не отсортирован, используйте линейный поиск. В этом случае сложность алгоритма будет равна 0(n).