[Играет музыка] ДАГ Lloyd: Линейный Поиск алгоритм мы можно использовать для поиска элемента в массиве. Алгоритм отзыв это шаг за шагом набор инструкций для выполнения задачи. 

Линейный поиск Алгоритм работает следующим образом. Итерации по массиву слева Право, глядя на указанном элементе. 

В псевдокоде, который является более дистиллированная версия этого предложения, Если первый элемент что Вы ищете, вы можете остановиться. В противном случае, перейти к следующему элементу и продолжать снова и снова до тех пор, пока не найдете элемент, или вы не делаете. Таким образом, мы можем использовать линейную Алгоритм поиска, например, найти целевое значение девять в этом массиве. Ну, мы начнем с самого начала. Если это то, что мы ищете, мы можем остановить. Это не так, мы не ищем 11. Так в противном случае, перейти к следующему элементу. 

Таким образом, мы смотрим на 23. 23 то, что мы ищем? Ну нет, так что мы перейдем к следующему элемент, а следующий элемент, и мы продолжаем переживает Этот процесс снова и снова, и более, пока мы не приземлиться по ситуации, как это. 

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

Но что, если мы ищем элемент, который не в массиве. Любая линейный поиск все еще работает? Хорошо обязательно. Таким образом, мы повторяем этот процесс начиная с первого элемента. Если это то, что мы ищете, мы можем остановить. Это не. В противном случае, мы переходим к следующему элементу. 

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

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

Это было неудачным, как сколько он не нашел 50, но 50 не в массиве. Но мы исчерпывающе искали через каждый отдельный элемент и так, пока мы не нашли что-нибудь, линейный поиск еще успешно, даже если элемент не в массиве. 

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

Что это говорит о Сложность линейного поиска? Ну в худшем случае, у нас есть посмотреть на каждый отдельный элемент. И так он работает в O из N, в худшем случае. 

В лучшем случае, мы собираемся сразу найти элемент. И так работает омега 1. 

Я Дуг Ллойд. Это CS50.