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

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: اولین چیزی که شما ممکن است
اطلاع در مورد پیدا کردن این است که ما در حال حاضر

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
انبار کاه برای یک سوزن کاربر را مشاهده کنید،
و این کار با تماس با مرتب کردن و

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
جستجو خطی در O از N اجرا
زمان است که کاملا آرام، با وجود آن که

21
00:01:11,610 --> 00:01:14,920
می توانید هر لیست داده شده به آن را جستجو کنید.

22
00:01:14,920 --> 00:01:21,190
کار شما این است برای اجرای جستجوی دودویی،
تا آن زمان 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
بازگشت درست است.

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
اند سوزن خود را پیدا نکرده است،
سپس شما بازگشت کاذب.

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