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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Perkara pertama yang anda mungkin
notis mengenai find ialah kita sudah

3
00:00:13,120 --> 00:00:14,520
telah kod bertulis untuk kita.

4
00:00:14,520 --> 00:00:16,219
Ini dipanggil kod pengedaran.

5
00:00:16,219 --> 00:00:19,060
Oleh itu, kita tidak hanya menulis kita sendiri
kod dari awal lagi.

6
00:00:19,060 --> 00:00:23,870
Sebaliknya, kami mengisi lompang
dalam beberapa kod yang sedia ada.

7
00:00:23,870 --> 00:00:28,860
>> Program find.c menggesa untuk nombor
untuk mengisi sisa rumput kering itu, mencari yang

8
00:00:28,860 --> 00:00:33,260
sisa rumput kering jarum pengguna dikemukakan,
dan ia melakukan ini dengan memanggil menyusun dan

9
00:00:33,260 --> 00:00:36,660
carian, fungsi yang ditakrif
dalam 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 untuk 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
Cari, yang mengembalikan benar jika nilai
terdapat dalam sisa rumput kering, kembali

15
00:00:50,110 --> 00:00:52,430
palsu jika nilai adalah
tidak dalam sisa rumput kering itu.

16
00:00:52,430 --> 00:00:59,060
Dan maka kita juga melaksanakan jenis,
yang mengisih tatasusunan dipanggil nilai-nilai.

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

18
00:01:01,120 --> 00:01:04,550
>> Cari kini dilaksanakan
sebagai carian linear.

19
00:01:04,550 --> 00:01:06,620
Tetapi anda boleh melakukan lebih baik daripada itu.

20
00:01:06,620 --> 00:01:11,610
Carian Linear dilaksanakan di O n
masa, yang agak perlahan, walaupun ia

21
00:01:11,610 --> 00:01:14,920
boleh mencari mana-mana senarai yang diberikan kepadanya.

22
00:01:14,920 --> 00:01:21,190
Tugas anda adalah untuk melaksanakan carian binari,
yang telah menjalankan masa O log n.

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

24
00:01:22,200 --> 00:01:24,240
>> Tetapi ada ketetapan yang.

25
00:01:24,240 --> 00:01:28,910
Carian binari hanya boleh mencari
melalui senarai pra-disusun.

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

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

28
00:01:33,690 --> 00:01:37,350
Memandangkan pelbagai nilai, sisa rumput kering itu,
kita akan mencari

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

30
00:01:41,510 --> 00:01:45,220
>> Cara bahawa carian binari berfungsi ialah
kita bandingkan nilai pertengahan

31
00:01:45,220 --> 00:01:49,430
array untuk jarum, sama seperti bagaimana
kami telah membuka buku telefon 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 selepas membandingkan nilai tengah untuk
jarum, anda boleh membuang sama ada

34
00:01:55,710 --> 00:01:59,620
kiri atau separuh betul array
dengan mengetatkan batas anda.

35
00:01:59,620 --> 00:02:04,450
Dalam kes ini, sejak 3, jarum kita,
kurang daripada 10, nilai menengah,

36
00:02:04,450 --> 00:02:07,060
betul terikat boleh berkurangan.

37
00:02:07,060 --> 00:02:09,470
>> Tetapi cuba untuk membuat batas anda
sebagai ketat yang mungkin.

38
00:02:09,470 --> 00:02:12,690
Jika nilai tengah bukan jarum,
maka anda tahu bahawa anda tidak perlu

39
00:02:12,690 --> 00:02:14,070
termasuk dalam carian anda.

40
00:02:14,070 --> 00:02:18,390
Jadi hak anda terikat boleh mengetatkan
batas carian hanya sedikit kecil lebih,

41
00:02:18,390 --> 00:02:22,840
dan sebagainya dan seterusnya, sehingga
anda mencari jarum anda.

42
00:02:22,840 --> 00:02:24,580
>> Jadi apa yang tidak pseudo
kod kelihatan seperti?

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

44
00:02:28,980 --> 00:02:33,540
unsur-unsur untuk mencari, kami mengambil tengah-tengah
senarai dan bandingkan yang

45
00:02:33,540 --> 00:02:36,020
nilai sederhana kepada jarum kami.

46
00:02:36,020 --> 00:02:38,380
Jika mereka sama, maka ini bermakna kita telah
didapati jarum, dan kita boleh

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

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

49
00:02:43,940 --> 00:02:48,350
boleh membuang separuh yang betul dan hanya
mencari sebelah kiri array.

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

51
00:02:51,860 --> 00:02:55,470
Dan pada akhirnya, jika anda tidak mempunyai apa-apa
lebih banyak unsur kiri untuk mencari tetapi anda

52
00:02:55,470 --> 00:02:58,030
tidak menemui jarum anda lagi,
maka anda pulangan palsu.

53
00:02:58,030 --> 00:03:02,960
Kerana jarum pasti
bukan dalam sisa rumput kering itu.

54
00:03:02,960 --> 00:03:06,200
>> Sekarang, satu perkara yang kemas mengenai pseudo ini
kod dalam carian binari adalah bahawa ia boleh

55
00:03:06,200 --> 00:03:11,000
ditafsirkan sebagai sama ada lelaran
atau pelaksanaan rekursif.

56
00:03:11,000 --> 00:03:14,900
Jadi ia akan menjadi rekursif jika anda dipanggil
fungsi carian dalam carian

57
00:03:14,900 --> 00:03:18,400
berfungsi pada sama ada separuh daripada array.

58
00:03:18,400 --> 00:03:20,750
Kami akan meliputi rekursi sedikit
kemudian dalam kursus ini.

59
00:03:20,750 --> 00:03:23,210
Tetapi tahu bahawa ia merupakan satu pilihan
jika anda ingin mencuba.

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