1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Hal pertama yang Anda mungkin
pemberitahuan tentang menemukan adalah bahwa kita sudah

3
00:00:13,120 --> 00:00:14,520
memiliki kode ditulis untuk kita.

4
00:00:14,520 --> 00:00:16,219
Ini disebut kode distribusi.

5
00:00:16,219 --> 00:00:19,060
Jadi kita tidak hanya menulis kita sendiri
kode dari awal lagi.

6
00:00:19,060 --> 00:00:23,870
Sebaliknya, kita mengisi rongga
dalam beberapa kode yang sudah ada.

7
00:00:23,870 --> 00:00:28,860
>> Program find.c meminta untuk nomor
untuk mengisi tumpukan jerami, akan mencari

8
00:00:28,860 --> 00:00:33,260
tumpukan jerami untuk jarum pengguna disampaikan,
dan hal ini dengan memanggil mengurutkan dan

9
00:00:33,260 --> 00:00:36,660
pencarian, fungsi didefinisikan
di helpers.c.

10
00:00:36,660 --> 00:00:38,740
Jadi find.c ditulis sudah.

11
00:00:38,740 --> 00:00:41,840
Tugas Anda adalah menulis pembantu.

12
00:00:41,840 --> 00:00:42,940
>> Jadi apa yang kita lakukan?

13
00:00:42,940 --> 00:00:45,270
Kami melaksanakan dua fungsi.

14
00:00:45,270 --> 00:00:50,110
Search, yang mengembalikan true jika nilai
ditemukan dalam tumpukan jerami, kembali

15
00:00:50,110 --> 00:00:52,430
false jika nilai adalah
bukan di tumpukan jerami.

16
00:00:52,430 --> 00:00:59,060
Dan kemudian kita juga menerapkan semacam,
yang macam array yang disebut nilai-nilai.

17
00:00:59,060 --> 00:01:01,120
Jadi mari kita menangani pencarian.

18
00:01:01,120 --> 00:01:04,550
>> Cari dilaksanakan saat ini
sebagai pencarian linear.

19
00:01:04,550 --> 00:01:06,620
Tapi Anda bisa melakukan jauh lebih baik dari itu.

20
00:01:06,620 --> 00:01:11,610
Pencarian linear diimplementasikan dalam O n
waktu, yang cukup lambat, meskipun

21
00:01:11,610 --> 00:01:14,920
dapat mencari daftar yang diberikan untuk itu.

22
00:01:14,920 --> 00:01:21,190
Tugas Anda adalah untuk melaksanakan pencarian biner,
yang telah berjalan waktu O dari log n.

23
00:01:21,190 --> 00:01:22,200
Itu cukup cepat.

24
00:01:22,200 --> 00:01:24,240
>> Tapi ada ketentuan a.

25
00:01:24,240 --> 00:01:28,910
Pencarian biner hanya dapat mencari
melalui daftar pra-diurutkan.

26
00:01:28,910 --> 00:01:31,450
Mengapa demikian?

27
00:01:31,450 --> 00:01:33,690
Nah, mari kita lihat sebuah contoh.

28
00:01:33,690 --> 00:01:37,350
Mengingat sebuah array nilai, tumpukan jerami,
kita akan melihat

29
00:01:37,350 --> 00:01:41,510
untuk jarum, dan dalam hal ini
Misalnya, integer 3.

30
00:01:41,510 --> 00:01:45,220
>> Cara bahwa pencarian biner bekerja adalah bahwa
kita membandingkan nilai tengah

31
00:01:45,220 --> 00:01:49,430
array ke jarum, seperti bagaimana
kami membuka buku telepon ke tengah

32
00:01:49,430 --> 00:01:51,720
Halaman dalam Minggu 0.

33
00:01:51,720 --> 00:01:55,710
Jadi setelah membandingkan nilai tengah untuk
jarum, Anda dapat membuang baik

34
00:01:55,710 --> 00:01:59,620
kiri atau kanan setengah dari array
dengan memperketat batas Anda.

35
00:01:59,620 --> 00:02:04,450
Dalam hal ini, sejak 3, jarum kita,
kurang dari 10, nilai tengah,

36
00:02:04,450 --> 00:02:07,060
benar terikat dapat menurunkan.

37
00:02:07,060 --> 00:02:09,470
>> Tapi cobalah untuk membuat batas Anda
seketat mungkin.

38
00:02:09,470 --> 00:02:12,690
Jika nilai tengah tidak jarum,
maka Anda tahu bahwa Anda tidak perlu

39
00:02:12,690 --> 00:02:14,070
memasukkannya dalam pencarian Anda.

40
00:02:14,070 --> 00:02:18,390
Jadi Anda benar terikat dapat mengencangkan
batas pencarian hanya sedikit lebih,

41
00:02:18,390 --> 00:02:22,840
dan seterusnya dan sebagainya, sampai
Anda menemukan jarum Anda.

42
00:02:22,840 --> 00:02:24,580
>> Jadi, apa pseudo
Kode terlihat seperti?

43
00:02:24,580 --> 00:02:28,980
Nah, sementara kita masih mencari melalui
daftar dan masih memiliki

44
00:02:28,980 --> 00:02:33,540
elemen untuk melihat ke dalam, kita mengambil tengah
daftar dan membandingkan

45
00:02:33,540 --> 00:02:36,020
nilai tengah untuk jarum kami.

46
00:02:36,020 --> 00:02:38,380
Jika mereka sama, maka itu berarti kita sudah
menemukan jarum, dan kita bisa

47
00:02:38,380 --> 00:02:40,160
kembali benar.

48
00:02:40,160 --> 00:02:43,940
>> Jika tidak, jika jarum kurang dari
nilai tengah, maka itu berarti kita

49
00:02:43,940 --> 00:02:48,350
bisa membuang setengah benar dan adil
mencari sisi kiri array.

50
00:02:48,350 --> 00:02:51,860
Jika tidak, kami akan mencari
sisi kanan dari array.

51
00:02:51,860 --> 00:02:55,470
Dan pada akhirnya, jika Anda tidak memiliki
lebih elemen yang tersisa untuk mencari tapi Anda

52
00:02:55,470 --> 00:02:58,030
belum menemukan jarum Anda belum,
maka Anda kembali palsu.

53
00:02:58,030 --> 00:03:02,960
Karena jarum pasti
tidak di tumpukan jerami.

54
00:03:02,960 --> 00:03:06,200
>> Sekarang, satu hal yang rapi tentang semu ini
kode dalam pencarian biner adalah bahwa hal itu dapat

55
00:03:06,200 --> 00:03:11,000
diartikan baik sebagai berulang
atau implementasi rekursif.

56
00:03:11,000 --> 00:03:14,900
Jadi akan rekursif jika Anda menelepon
fungsi pencarian dalam pencarian

57
00:03:14,900 --> 00:03:18,400
berfungsi di kedua setengah dari array.

58
00:03:18,400 --> 00:03:20,750
Kita akan membahas rekursi sedikit
kemudian dalam kursus.

59
00:03:20,750 --> 00:03:23,210
Tapi jangan tahu bahwa itu adalah pilihan
jika Anda ingin mencoba.

60
00:03:23,210 --> 00:03:24,460