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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA陳：首先，你可能會
通知有關的發現是，我們已經

3
00:00:13,120 --> 00:00:14,520
已編寫的代碼我們。

4
00:00:14,520 --> 00:00:16,219
這就是所謂的分配的代碼。

5
00:00:16,219 --> 00:00:19,060
所以，我們不只是編寫我們自己的
從頭開始編寫代碼了。

6
00:00:19,060 --> 00:00:23,870
相反，我們正在填補空隙
在某些預先存在的代碼。

7
00:00:23,870 --> 00:00:28,860
>> 該find.c程序會提示輸入數字
填補了草垛，搜索

8
00:00:28,860 --> 00:00:33,260
在haystack一個用戶提交的針，
它是通過調用排序和

9
00:00:33,260 --> 00:00:36,660
定義的搜索，函數
在helpers.c。

10
00:00:36,660 --> 00:00:38,740
所以find.c已經寫入。

11
00:00:38,740 --> 00:00:41,840
你的任務是寫傭工。

12
00:00:41,840 --> 00:00:42,940
>> 所以我們在做什麼？

13
00:00:42,940 --> 00:00:45,270
我們正在實施兩種功能。

14
00:00:45,270 --> 00:00:50,110
搜索，返回true，如果一個值
在草垛被發現，返回

15
00:00:50,110 --> 00:00:52,430
假如果該值
不是在幹草堆。

16
00:00:52,430 --> 00:00:59,060
然後我們也實施排序，
這所謂的排序值數組。

17
00:00:59,060 --> 00:01:01,120
因此，讓我們來解決搜索。

18
00:01:01,120 --> 00:01:04,550
>> 搜索目前已實施
作為一個線性搜索。

19
00:01:04,550 --> 00:01:06,620
但是你可以做的比這更好的。

20
00:01:06,620 --> 00:01:11,610
線性搜索是在n個鄰實施
時間，這是相當緩慢的，儘管它

21
00:01:11,610 --> 00:01:14,920
可以搜索給它的任何列表。

22
00:01:14,920 --> 00:01:21,190
你的任務是實現二分查找，
已運行日誌的n時間為O。

23
00:01:21,190 --> 00:01:22,200
這是相當快的。

24
00:01:22,200 --> 00:01:24,240
>> 但是有一個規定。

25
00:01:24,240 --> 00:01:28,910
二進制搜索只能搜索
通過預排序的列表。

26
00:01:28,910 --> 00:01:31,450
這是為什麼？

27
00:01:31,450 --> 00:01:33,690
那麼，讓我們來看一個例子。

28
00:01:33,690 --> 00:01:37,350
給定的值的數組，草垛，
我們要去尋找

29
00:01:37,350 --> 00:01:41,510
一針，在這
例如，整數3。

30
00:01:41,510 --> 00:01:45,220
>> 二進制搜索的工作方式是，
我們比較的中間值

31
00:01:45,220 --> 00:01:49,430
陣列到針，很像如何
我們開了一個電話簿中間

32
00:01:49,430 --> 00:01:51,720
在週0頁。

33
00:01:51,720 --> 00:01:55,710
所以中間值相比較之後
針，你可以放棄任

34
00:01:55,710 --> 00:01:59,620
左或陣列的右半
收緊你的界限。

35
00:01:59,620 --> 00:02:04,450
在這種情況下，由於3，我們的針，是
小於10時，中間值，該

36
00:02:04,450 --> 00:02:07,060
右邊界會降低。

37
00:02:07,060 --> 00:02:09,470
>> 但盡量讓你的界限
盡可能緊。

38
00:02:09,470 --> 00:02:12,690
如果中間值不是針
那麼你知道，你並不需要

39
00:02:12,690 --> 00:02:14,070
它包含在你的搜索。

40
00:02:14,070 --> 00:02:18,390
所以，你的權利綁定可以收緊
搜索範圍更多的只是一點點，

41
00:02:18,390 --> 00:02:22,840
等等等等，直到
你發現你的針。

42
00:02:22,840 --> 00:02:24,580
>> 那麼什麼是偽
代碼是什麼樣子？

43
00:02:24,580 --> 00:02:28,980
好了，而我們仍然在尋找通過
列表中，仍然有

44
00:02:28,980 --> 00:02:33,540
元素在看，我們取中間
列表和比較

45
00:02:33,540 --> 00:02:36,020
中間的價值，我們的針。

46
00:02:36,020 --> 00:02:38,380
如果他們是平等的，那麼這意味著我們已經
發現針，大家可以

47
00:02:38,380 --> 00:02:40,160
返回true。

48
00:02:40,160 --> 00:02:43,940
>> 否則，如果針小於
的中間值，那麼這意味著我們

49
00:02:43,940 --> 00:02:48,350
可以丟棄的右半邊，只是
搜索數組的左側。

50
00:02:48,350 --> 00:02:51,860
否則，我們將搜索
右側的數組。

51
00:02:51,860 --> 00:02:55,470
並在結束時，如果你沒有任何
留下來搜索更多的元素，但你

52
00:02:55,470 --> 00:02:58,030
有沒有發現你的針還，
那麼你返回false。

53
00:02:58,030 --> 00:03:02,960
因為針絕對
是不是在幹草堆。

54
00:03:02,960 --> 00:03:06,200
>> 現在，人們整齊一點關於這個偽
在二分搜索代碼是，它可以

55
00:03:06,200 --> 00:03:11,000
被解釋為一個迭代
或遞歸實現。

56
00:03:11,000 --> 00:03:14,900
因此，這將是遞歸的，如果你叫
在搜索中的搜索功能

57
00:03:14,900 --> 00:03:18,400
功能上無論是數組的一半。

58
00:03:18,400 --> 00:03:20,750
我們將介紹遞歸位
在後面的過程。

59
00:03:20,750 --> 00:03:23,210
但是知道它是一個選項
如果你想嘗試。

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