1
00:00:00,000 --> 00:00:02,892
>> [Играет музыка]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
ДАГ Lloyd: Линейный
Поиск алгоритм мы

4
00:00:07,180 --> 00:00:09,840
можно использовать для поиска элемента в массиве.

5
00:00:09,840 --> 00:00:11,990
Алгоритм отзыв
это шаг за шагом набор

6
00:00:11,990 --> 00:00:15,030
инструкций для выполнения задачи.

7
00:00:15,030 --> 00:00:17,480
>> Линейный поиск
Алгоритм работает следующим образом.

8
00:00:17,480 --> 00:00:22,200
Итерации по массиву слева
Право, глядя на указанном элементе.

9
00:00:22,200 --> 00:00:26,380
>> В псевдокоде, который является более
дистиллированная версия этого предложения,

10
00:00:26,380 --> 00:00:29,840
Если первый элемент что
Вы ищете, вы можете остановиться.

11
00:00:29,840 --> 00:00:33,930
В противном случае, перейти к следующему элементу и
продолжать снова и снова до тех пор, пока не найдете

12
00:00:33,930 --> 00:00:36,389
элемент, или вы не делаете.

13
00:00:36,389 --> 00:00:38,680
Таким образом, мы можем использовать линейную
Алгоритм поиска, например,

14
00:00:38,680 --> 00:00:42,330
найти целевое значение
девять в этом массиве.

15
00:00:42,330 --> 00:00:43,870
Ну, мы начнем с самого начала.

16
00:00:43,870 --> 00:00:45,970
Если это то, что мы
ищете, мы можем остановить.

17
00:00:45,970 --> 00:00:47,890
Это не так, мы не ищем 11.

18
00:00:47,890 --> 00:00:50,220
Так в противном случае, перейти к следующему элементу.

19
00:00:50,220 --> 00:00:51,510
>> Таким образом, мы смотрим на 23.

20
00:00:51,510 --> 00:00:52,730
23 то, что мы ищем?

21
00:00:52,730 --> 00:00:55,614
Ну нет, так что мы перейдем к следующему
элемент, а следующий элемент,

22
00:00:55,614 --> 00:00:57,780
и мы продолжаем переживает
Этот процесс снова и снова,

23
00:00:57,780 --> 00:01:01,030
и более, пока мы не приземлиться
по ситуации, как это.

24
00:01:01,030 --> 00:01:03,910
>> Девять то, что мы ищем,
и этот элемент массива

25
00:01:03,910 --> 00:01:05,787
есть, это значение составляет девять.

26
00:01:05,787 --> 00:01:08,120
И таким образом, мы нашли то, что мы
ищете, и мы можем остановиться.

27
00:01:08,120 --> 00:01:11,910
Линейный поиск имеет
завершено успешно.

28
00:01:11,910 --> 00:01:15,370
>> Но что, если мы ищем
элемент, который не в массиве.

29
00:01:15,370 --> 00:01:17,040
Любая линейный поиск все еще работает?

30
00:01:17,040 --> 00:01:17,540
Хорошо обязательно.

31
00:01:17,540 --> 00:01:19,947
Таким образом, мы повторяем этот процесс
начиная с первого элемента.

32
00:01:19,947 --> 00:01:21,780
Если это то, что мы
ищете, мы можем остановить.

33
00:01:21,780 --> 00:01:22,800
Это не.

34
00:01:22,800 --> 00:01:25,020
В противном случае, мы переходим к следующему элементу.

35
00:01:25,020 --> 00:01:29,050
>> Но мы можем повторять этот процесс,
рассматривая каждый элемент, в свою очередь,

36
00:01:29,050 --> 00:01:31,720
надеясь, что мы находим числа 50.

37
00:01:31,720 --> 00:01:33,750
Но мы не будете знать, если
мы нашли номер 50

38
00:01:33,750 --> 00:01:38,290
или если мы не сделали, пока мы не вышел
над каждым одного элемента массива.

39
00:01:38,290 --> 00:01:40,440
>> Только один раз мы сделали
что и придумать короткий,

40
00:01:40,440 --> 00:01:43,040
мы можем сделать вывод, что
50 не находится в массиве.

41
00:01:43,040 --> 00:01:46,410
И поэтому линейный поиск
Алгоритм, также он не по себе.

42
00:01:46,410 --> 00:01:49,181
Но не в том смысле, что это
была неудачной в этом, что

43
00:01:49,181 --> 00:01:49,930
мы попросили его сделать.

44
00:01:49,930 --> 00:01:52,390
>> Это было неудачным, как
сколько он не нашел 50,

45
00:01:52,390 --> 00:01:54,070
но 50 не в массиве.

46
00:01:54,070 --> 00:01:57,310
Но мы исчерпывающе искали
через каждый отдельный элемент

47
00:01:57,310 --> 00:02:00,550
и так, пока мы не нашли
что-нибудь, линейный поиск еще

48
00:02:00,550 --> 00:02:05,230
успешно, даже если
элемент не в массиве.

49
00:02:05,230 --> 00:02:07,507
>> Так что в худшем случае
Сценарий с линейным поиском?

50
00:02:07,507 --> 00:02:09,590
Ну, мы должны смотреть через
каждый элемент,

51
00:02:09,590 --> 00:02:14,590
либо потому, что целевой элемент
это последний элемент массива,

52
00:02:14,590 --> 00:02:18,510
или элемент, мы ищем не
на самом деле существует в массиве на всех.

53
00:02:18,510 --> 00:02:19,760
Какой самый лучший сценарий?

54
00:02:19,760 --> 00:02:22,430
Ну, мы могли бы найти
элемент немедленно.

55
00:02:22,430 --> 00:02:24,360
И сколько элементов
Итак, мы должны смотреть

56
00:02:24,360 --> 00:02:26,859
на, в лучшем случае,
если мы ищем для него

57
00:02:26,859 --> 00:02:28,400
и мы находим его в самом начале?

58
00:02:28,400 --> 00:02:29,850
Мы можем остановить немедленно.

59
00:02:29,850 --> 00:02:32,984
>> Что это говорит о
Сложность линейного поиска?

60
00:02:32,984 --> 00:02:35,650
Ну в худшем случае, у нас есть
посмотреть на каждый отдельный элемент.

61
00:02:35,650 --> 00:02:38,930
И так он работает в O из
N, в худшем случае.

62
00:02:38,930 --> 00:02:41,540
>> В лучшем случае, мы собираемся
сразу найти элемент.

63
00:02:41,540 --> 00:02:44,750
И так работает омега 1.

64
00:02:44,750 --> 00:02:45,780
>> Я Дуг Ллойд.

65
00:02:45,780 --> 00:02:48,020
Это CS50.

66
00:02:48,020 --> 00:02:49,876