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