1
00:00:00,000 --> 00:00:02,892
>> [Bermain muzik]

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

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Linear
carian adalah kita algoritma

4
00:00:07,180 --> 00:00:09,840
boleh gunakan untuk mencari satu elemen dalam array.

5
00:00:09,840 --> 00:00:11,990
Yang ingat algoritma
adalah satu set langkah-demi-langkah

6
00:00:11,990 --> 00:00:15,030
arahan untuk menyiapkan tugas.

7
00:00:15,030 --> 00:00:17,480
>> Pencarian linear
algoritma berfungsi seperti berikut.

8
00:00:17,480 --> 00:00:22,200
Melelar seluruh array dari kiri ke
betul, mencari elemen yang ditetapkan.

9
00:00:22,200 --> 00:00:26,380
>> Dalam kod pseudo, yang merupakan lebih
versi suling ayat ini,

10
00:00:26,380 --> 00:00:29,840
jika elemen pertama adalah apa yang
anda cari, anda boleh berhenti.

11
00:00:29,840 --> 00:00:33,930
Jika tidak, bergerak ke elemen yang akan datang dan
terus pergi berulang-ulang sehingga anda mencari

12
00:00:33,930 --> 00:00:36,389
unsur, atau anda tidak.

13
00:00:36,389 --> 00:00:38,680
Oleh itu, kita boleh menggunakan linear
algoritma carian, sebagai contoh,

14
00:00:38,680 --> 00:00:42,330
untuk mencari nilai sasaran
sembilan dalam pelbagai ini.

15
00:00:42,330 --> 00:00:43,870
Baik kita mulakan pada permulaan.

16
00:00:43,870 --> 00:00:45,970
Jika ia adalah apa yang kita
cari, kami boleh berhenti.

17
00:00:45,970 --> 00:00:47,890
Ia tidak, kita tidak mencari 11.

18
00:00:47,890 --> 00:00:50,220
Jadi jika tidak, bergerak ke elemen seterusnya.

19
00:00:50,220 --> 00:00:51,510
>> Oleh itu, kita melihat 23.

20
00:00:51,510 --> 00:00:52,730
Adalah 23 apa yang kami cari?

21
00:00:52,730 --> 00:00:55,614
Yah tidak, jadi kita bergerak ke depan
unsur unsur yang akan datang,

22
00:00:55,614 --> 00:00:57,780
dan kami terus melalui
proses ini berulang-ulang

23
00:00:57,780 --> 00:01:01,030
dan ke atas, sehingga kita tanah
pada keadaan seperti ini.

24
00:01:01,030 --> 00:01:03,910
>> Sembilan adalah apa yang kita cari,
dan elemen ini array

25
00:01:03,910 --> 00:01:05,787
adalah, nilai itu adalah sembilan.

26
00:01:05,787 --> 00:01:08,120
Dan dengan itu kita mendapati apa yang kita
cari, dan kita boleh berhenti.

27
00:01:08,120 --> 00:01:11,910
Pencarian linear mempunyai
selesai, dengan jayanya.

28
00:01:11,910 --> 00:01:15,370
>> Tetapi bagaimana pula jika kita cari
unsur yang bukan dalam pelbagai kami.

29
00:01:15,370 --> 00:01:17,040
Adakah carian linear masih berfungsi?

30
00:01:17,040 --> 00:01:17,540
Nah pasti.

31
00:01:17,540 --> 00:01:19,947
Oleh itu, kita mengulangi proses ini
bermula dari elemen pertama.

32
00:01:19,947 --> 00:01:21,780
Jika ia adalah apa yang kita
cari, kami boleh berhenti.

33
00:01:21,780 --> 00:01:22,800
Ianya bukan.

34
00:01:22,800 --> 00:01:25,020
Jika tidak, kita beralih kepada elemen seterusnya.

35
00:01:25,020 --> 00:01:29,050
>> Tetapi kita boleh terus mengulangi proses ini,
memeriksa setiap elemen seterusnya,

36
00:01:29,050 --> 00:01:31,720
berharap bahawa kita mencari nombor 50.

37
00:01:31,720 --> 00:01:33,750
Tetapi kita tidak akan tahu jika
kami telah mendapati jumlah 50

38
00:01:33,750 --> 00:01:38,290
atau jika kita tidak, sehingga kita telah melangkah
ke atas setiap elemen tunggal array.

39
00:01:38,290 --> 00:01:40,440
>> Hanya sekali yang telah kami lakukan
itu dan datang sehingga pendek,

40
00:01:40,440 --> 00:01:43,040
boleh kita membuat kesimpulan bahawa
50 tidak ada di dalam array.

41
00:01:43,040 --> 00:01:46,410
Dan sebagainya carian linear
algoritma, dan ia gagal, per se.

42
00:01:46,410 --> 00:01:49,181
Tetapi tidak dalam erti kata bahawa ia
tidak berjaya melakukannya,

43
00:01:49,181 --> 00:01:49,930
kami bertanya ia lakukan.

44
00:01:49,930 --> 00:01:52,390
>> Ia tidak berjaya masuk sebagai
banyak kerana ia tidak mendapati 50,

45
00:01:52,390 --> 00:01:54,070
tetapi 50 tidak dalam array.

46
00:01:54,070 --> 00:01:57,310
Tetapi kita telah mendalam dicari
melalui setiap elemen tunggal

47
00:01:57,310 --> 00:02:00,550
dan sebagainya, sementara kami tidak menjumpai
apa-apa, carian linear masih

48
00:02:00,550 --> 00:02:05,230
berjaya walaupun
unsur bukan dalam array.

49
00:02:05,230 --> 00:02:07,507
>> Jadi apa kes yang paling teruk
senario dengan carian linear?

50
00:02:07,507 --> 00:02:09,590
Baik kita perlu melihat melalui
setiap elemen tunggal,

51
00:02:09,590 --> 00:02:14,590
sama ada kerana elemen sasaran
adalah elemen terakhir array,

52
00:02:14,590 --> 00:02:18,510
atau unsur yang kita cari tidak
benar-benar wujud dalam array sama sekali.

53
00:02:18,510 --> 00:02:19,760
Apakah senario kes terbaik?

54
00:02:19,760 --> 00:02:22,430
Baik kita mungkin mendapati
unsur dengan segera.

55
00:02:22,430 --> 00:02:24,360
Dan berapa banyak unsur-unsur
kita kemudian perlu melihat

56
00:02:24,360 --> 00:02:26,859
di dalam kes ini,
jika kita mencari untuk itu

57
00:02:26,859 --> 00:02:28,400
dan kami menemuinya di awal-awal lagi?

58
00:02:28,400 --> 00:02:29,850
Kita boleh berhenti serta-merta.

59
00:02:29,850 --> 00:02:32,984
>> Apakah ini mengatakan mengenai
kerumitan carian linear?

60
00:02:32,984 --> 00:02:35,650
Baik dalam kes paling teruk, kita ada
untuk melihat setiap elemen tunggal.

61
00:02:35,650 --> 00:02:38,930
Dan supaya ia berjalan di O
n, dalam kes yang paling teruk.

62
00:02:38,930 --> 00:02:41,540
>> Dalam kes ini, kita akan
mencari elemen dengan segera.

63
00:02:41,540 --> 00:02:44,750
Dan supaya berjalan dalam omega 1.

64
00:02:44,750 --> 00:02:45,780
>> Saya Doug Lloyd.

65
00:02:45,780 --> 00:02:48,020
Ini adalah CS50.

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