1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> რობ Bowden: Hi, მე Rob.

3
00:00:15,010 --> 00:00:16,790
როგორ უნდა დაასაქმოს ორობითი ძებნა?

4
00:00:16,790 --> 00:00:18,770
მოდით გავარკვიოთ.

5
00:00:18,770 --> 00:00:23,400
ასე რომ, გაითვალისწინოთ, რომ ძიების ჩვენ ვაპირებთ
განახორციელოს რეკურსიული.

6
00:00:23,400 --> 00:00:27,470
თქვენ შეიძლება ასევე განახორციელოს ორობითი ძებნა
iteratively ასე რომ, თუ თქვენ გააკეთეთ, რომ,

7
00:00:27,470 --> 00:00:29,280
რომ შესანიშნავად ჯარიმა.

8
00:00:29,280 --> 00:00:32,820
>> ახლა პირველი, გავიხსენოთ რა
პარამეტრების ძებნა ნიშნავდა იყოს.

9
00:00:32,820 --> 00:00:36,120
აქ ჩვენ ვხედავთ int ღირებულება, რომელიც
უნდა იყოს ღირებულება მომხმარებელი

10
00:00:36,120 --> 00:00:37,320
ეძებს.

11
00:00:37,320 --> 00:00:40,800
ჩვენ ვხედავთ int ღირებულებებს მასივი, რომელიც
არის array, რომელიც ჩვენ

12
00:00:40,800 --> 00:00:42,520
ეძებს ღირებულება.

13
00:00:42,520 --> 00:00:45,602
და ჩვენ ვხედავთ int n, რომელიც
ხანგრძლივობა ჩვენი მასივი.

14
00:00:45,602 --> 00:00:47,410
>> ახლა, პირველი, რაც პირველი.

15
00:00:47,410 --> 00:00:51,350
ჩვენ შეამოწმეთ თუ n უდრის 0, in
ასეთ შემთხვევაში ჩვენ დაბრუნების ცრუ.

16
00:00:51,350 --> 00:00:54,770
რომ უბრალოდ ვამბობ, თუ ჩვენ ცარიელი
მასივი, ღირებულება აშკარად არ

17
00:00:54,770 --> 00:00:57,860
ცარიელი მასივი, ასე რომ ჩვენ შეგვიძლია დაბრუნების ცრუ.

18
00:00:57,860 --> 00:01:01,250
>> ახლა ჩვენ რეალურად გვინდა გავაკეთოთ ორობითი
ძებნის ნაწილი ორობითი ძებნა.

19
00:01:01,250 --> 00:01:04,780
ასე რომ, ჩვენ გვსურს მოვძებნოთ შუა
ელემენტს ამ მასივი.

20
00:01:04,780 --> 00:01:09,130
აქ, ჩვენ ვამბობთ, შუა შეადგენს n იყოფა
2, რადგან შუა ელემენტს

21
00:01:09,130 --> 00:01:12,240
იქნება ხანგრძლივობა
ჩვენს მასივი იყოფა 2.

22
00:01:12,240 --> 00:01:15,040
ახლა ჩვენ ვაპირებთ, რათა შეამოწმოს, თუ
შუა ელემენტს შეადგენს ღირებულება ვართ

23
00:01:15,040 --> 00:01:16,160
ეძებს.

24
00:01:16,160 --> 00:01:21,030
ასე რომ, თუ ღირებულებების შუა უტოლდება ღირებულება, ჩვენ
შეუძლია დაბრუნდეს ჭეშმარიტი, რადგან აღმოვაჩინეთ

25
00:01:21,030 --> 00:01:22,810
ღირებულება ჩვენს მასივი.

26
00:01:22,810 --> 00:01:26,380
>> მაგრამ თუ ეს არ იყო მართალი, ახლა
ჩვენ უნდა გავაკეთოთ რეკურსიული

27
00:01:26,380 --> 00:01:27,840
ნაბიჯი ორობითი ძებნა.

28
00:01:27,840 --> 00:01:30,450
ჩვენ უნდა მოძებნოთ ან
მარცხენა მასივი ან

29
00:01:30,450 --> 00:01:32,320
შუა მასივი.

30
00:01:32,320 --> 00:01:39,280
ასე რომ აქ, ჩვენ ვამბობთ, თუ ღირებულებები შუა არის
ნაკლები ღირებულება, რაც იმას ნიშნავს, რომ ღირებულება

31
00:01:39,280 --> 00:01:41,350
იყო უფრო მეტი, ვიდრე შუა
მასივი.

32
00:01:41,350 --> 00:01:45,790
ასე რომ მნიშვნელობა უნდა იყოს მარჯვნივ
ელემენტს, რომ ჩვენ უბრალოდ შევხედე.

33
00:01:45,790 --> 00:01:48,090
>> ასე რომ აქ, ჩვენ ვაპირებთ
ძებნის რეკურსიული.

34
00:01:48,090 --> 00:01:50,320
და ჩვენ შევხედოთ რაც ჩვენ გავლის
ამ მეორე.

35
00:01:50,320 --> 00:01:53,440
მაგრამ ჩვენ ვაპირებთ ძიება
მარჯვენა შუა ელემენტს.

36
00:01:53,440 --> 00:01:57,710
და სხვა შემთხვევაში ეს ნიშნავს, რომ
ღირებულება ნაკლები იყო შუა

37
00:01:57,710 --> 00:02:00,660
მასივი, და ამიტომ ჩვენ ვაპირებთ
ძებნის მარცხენა.

38
00:02:00,660 --> 00:02:03,520
ახლა, მარცხენა იქნება
ცოტა ადვილია შევხედოთ.

39
00:02:03,520 --> 00:02:07,770
ასე რომ, ჩვენ ვხედავთ, რომ ჩვენ რეკურსიული
მოუწოდებდა ძებნა, სადაც პირველი

40
00:02:07,770 --> 00:02:10,120
არგუმენტი, კიდევ ერთხელ, ღირებულება
ჩვენ ვეძებთ მეტი.

41
00:02:10,120 --> 00:02:14,970
მეორე არგუმენტი იქნება
array, რომ ჩვენ ძებნას დასრულდა.

42
00:02:14,970 --> 00:02:17,090
და ბოლო ელემენტი არის ცენტრიდან.

43
00:02:17,090 --> 00:02:21,650
მახსოვს ბოლო პარამეტრი არის ჩვენი int
n, ასე რომ სიგრძეზე ჩვენი მასივი.

44
00:02:21,650 --> 00:02:25,310
>> ამ რეკურსიული ზარი მოძიება, ჩვენ
ახლა განაცხადა, რომ სიგრძეზე

45
00:02:25,310 --> 00:02:27,230
array არის ცენტრიდან.

46
00:02:27,230 --> 00:02:32,900
ასე რომ, თუ ჩვენი მასივი იყო ზომა 20 და ჩვენ
ჩხრეკა საათზე ინდექსი 10, მას შემდეგ, რაც შუა არის

47
00:02:32,900 --> 00:02:36,930
20 იყოფა 2, ეს ნიშნავს, რომ ჩვენ
გავლით 10, როგორც ახალი

48
00:02:36,930 --> 00:02:38,300
ხანგრძლივობა ჩვენი მასივი.

49
00:02:38,300 --> 00:02:41,910
გახსოვდეთ, რომ როდესაც თქვენ გაქვთ მასივი
სიგრძე 10, ეს ნიშნავს, რომ მოქმედი

50
00:02:41,910 --> 00:02:45,450
ელემენტები ინდექსების 0 მეშვეობით 9.

51
00:02:45,450 --> 00:02:50,120
ასე რომ, ეს არის ის, რაც ჩვენ გვინდა
მიუთითოთ ჩვენი ახლდება მასივი - მარცხენა

52
00:02:50,120 --> 00:02:53,010
array შუა ელემენტს.

53
00:02:53,010 --> 00:02:55,710
>> ასე რომ, ეძებს მარჯვნივ არის
ცოტა უფრო რთული.

54
00:02:55,710 --> 00:03:00,170
ახლა პირველ რიგში, განვიხილოთ სიგრძე
მასივი მარჯვნივ

55
00:03:00,170 --> 00:03:01,240
შუა ელემენტს.

56
00:03:01,240 --> 00:03:08,390
ასე რომ, თუ ჩვენი მასივი იყო size n, მაშინ
ახალი მასივი იქნება ზომის n minus

57
00:03:08,390 --> 00:03:10,140
შუა მინუს 1.

58
00:03:10,140 --> 00:03:12,530
ასე რომ, მოდით ვიფიქროთ n მინუს ცენტრიდან.

59
00:03:12,530 --> 00:03:18,710
>> ისევ და ისევ, თუ array იყო ზომა 20
ჩვენ გაყოფა 2 მისაღებად შუა,

60
00:03:18,710 --> 00:03:23,540
ასე რომ, შუა არის 10, მაშინ n მინუს შუა
აპირებს მოგვცეს 10, ისე 10

61
00:03:23,540 --> 00:03:25,330
ელემენტები მარჯვნივ ცენტრიდან.

62
00:03:25,330 --> 00:03:27,780
მაგრამ ჩვენ ასევე გვაქვს ამ minus
1, რადგან ჩვენ არ გვინდა, რომ

63
00:03:27,780 --> 00:03:29,700
მოიცავს შუა თავად.

64
00:03:29,700 --> 00:03:34,190
ასე n მინუს შუა მინუს 1 გვაძლევს
საერთო რაოდენობის ელემენტების უფლება

65
00:03:34,190 --> 00:03:36,800
შუა ინდექსი მასივი.

66
00:03:36,800 --> 00:03:41,870
>> ახლა აქ, გახსოვდეთ, რომ შუა
პარამეტრი ღირებულებების მასივი.

67
00:03:41,870 --> 00:03:46,180
ასე რომ აქ, ჩვენ ავლით
განახლდა ღირებულებების მასივი.

68
00:03:46,180 --> 00:03:50,930
ეს ფასეულობები, პლუს შუა plus 1
რეალურად ამბობდა რეკურსიული დარეკეთ

69
00:03:50,930 --> 00:03:56,460
ძებნა გავლით ახალი მასივი, სადაც
რომ ახალი მასივი იწყება შუა

70
00:03:56,460 --> 00:03:59,370
პლუს ერთი ჩვენი ორიგინალური ღირებულებებს მასივი.

71
00:03:59,370 --> 00:04:05,400
>> ალტერნატიული სინტაქსი, რომ ახლა,
თქვენ დაიწყო, რომ ნახოთ პოინტერები, არის

72
00:04:05,400 --> 00:04:10,170
ampersand ღირებულებების შუა პლუს 1.

73
00:04:10,170 --> 00:04:17,149
ასე რომ, დაიბრუნოს მისამართი ცენტრიდან
პლუს ერთი ელემენტია ღირებულებებს.

74
00:04:17,149 --> 00:04:23,690
>> ახლა კი, თუ არ იყო კომფორტული
შეცვლის მასივი, როგორიცაა, რომ თქვენ

75
00:04:23,690 --> 00:04:28,900
ასევე შეიძლება არ განხორციელდა ამ გამოყენებით
რეკურსიული დამხმარე ფუნქცია, სადაც

76
00:04:28,900 --> 00:04:31,680
რომ დამხმარე ფუნქცია იღებს
მეტი არგუმენტები.

77
00:04:31,680 --> 00:04:36,610
ასე რომ ნაცვლად მიღების მხოლოდ ღირებულება,
მასივი, და ზომა მასივი,

78
00:04:36,610 --> 00:04:42,315
დამხმარე ფუნქცია შეიძლება მიიღოს მეტი
არგუმენტები, მათ შორის ქვედა ინდექსი

79
00:04:42,315 --> 00:04:45,280
რომ თქვენ აინტერესებს მასივი
და ზედა ინდექსი, რომ თქვენ ზრუნვა

80
00:04:45,280 --> 00:04:46,300
შესახებ მასივი.

81
00:04:46,300 --> 00:04:49,770
>> და ასე შენახვა ტრეკზე ორივე ქვედა
ინდექსი და ზედა ინდექსი, თქვენ არ

82
00:04:49,770 --> 00:04:52,780
უნდა ოდესმე ცვლილებები
ორიგინალური ღირებულებებს მასივი.

83
00:04:52,780 --> 00:04:56,390
შეგიძლიათ უბრალოდ გააგრძელებს
მნიშვნელობები გამოვიყენოთ მასივი.

84
00:04:56,390 --> 00:04:59,540
მაგრამ აქ, შეამჩნია ჩვენ არ გვჭირდება დამხმარე
ფუნქციონირებს, რადგან ჩვენ

85
00:04:59,540 --> 00:05:01,760
სურვილი ცვლილებები ორიგინალური
ღირებულებები მასივი.

86
00:05:01,760 --> 00:05:05,020
ჩვენ მზად უნდა გაიაროს
განახლებული ღირებულებებს.

87
00:05:05,020 --> 00:05:09,140
>> ახლა, ჩვენ ვერ ორობითი ძებნა მეტი
მასივი, რომელიც არის დაუხარისხებელი.

88
00:05:09,140 --> 00:05:12,220
ასე რომ, მოდით მიიღოს ამ დახარისხებული out.

89
00:05:12,220 --> 00:05:17,650
ახლა შეამჩნია, რომ დალაგების არის ბოლო ორი
პარამეტრები int ღირებულებებს, რომელიც

90
00:05:17,650 --> 00:05:21,110
array, რომ ჩვენ დახარისხება და int n,
რომელიც არის სიგრძეზე მასივი,

91
00:05:21,110 --> 00:05:22,250
ჩვენ დახარისხება.

92
00:05:22,250 --> 00:05:24,840
ასე რომ, აქ ჩვენ გვინდა განხორციელება
დახარისხება ალგორითმი

93
00:05:24,840 --> 00:05:26,690
რომ არის o of n კვადრატში.

94
00:05:26,690 --> 00:05:30,560
თქვენ შეიძლება აირჩიონ bubble sort, შერჩევა
დალაგების ან Insertion დალაგების, ან

95
00:05:30,560 --> 00:05:32,670
რამდენიმე სხვა სახის არ გვაქვს
ჩანს კლასი.

96
00:05:32,670 --> 00:05:36,380
მაგრამ აქ, ჩვენ ვაპირებთ
გამოყენება შერჩევის ჯიშია.

97
00:05:36,380 --> 00:05:40,030
>> ასე რომ, ჩვენ ვაპირებთ iterate
მთელ მასივი.

98
00:05:40,030 --> 00:05:44,360
ისე, აქ ჩვენ ვხედავთ, რომ ჩვენ iterating
0 დან n მინუს 1.

99
00:05:44,360 --> 00:05:45,990
რატომ არ არის ყველა გზა მდე n?

100
00:05:45,990 --> 00:05:49,320
ისე, თუ ჩვენ უკვე დახარისხებული პირველი
n მინუს 1 ელემენტები, მაშინ

101
00:05:49,320 --> 00:05:54,420
ძალიან ბოლო ელემენტს რა უნდა გადახვიდეთ
სწორი ადგილი, ასე დახარისხება მეტი

102
00:05:54,420 --> 00:05:56,520
მთელი მასივი.

103
00:05:56,520 --> 00:05:58,770
>> ახლა, მახსოვს, როგორ შერჩევა
სახის სამუშაოები.

104
00:05:58,770 --> 00:06:01,950
ჩვენ ვაპირებთ წავიდეთ მთელ მასივი
ეძებს მინიმალური ღირებულება

105
00:06:01,950 --> 00:06:04,480
მასივი და ჯოხი, რომ
დასაწყისში.

106
00:06:04,480 --> 00:06:07,610
მაშინ ჩვენ ვაპირებთ წავიდეთ მთელ
array ისევ ეძებს მეორე

107
00:06:07,610 --> 00:06:10,410
პატარა ელემენტი, და ჯოხი, რომ
მეორე პოზიცია

108
00:06:10,410 --> 00:06:12,100
მასივი, და ასე შემდეგ.

109
00:06:12,100 --> 00:06:14,330
ასე რომ, ის, რაც ამ აკეთებს.

110
00:06:14,330 --> 00:06:17,290
>> აქ ჩვენ ვხედავთ, რომ ჩვენ
შექმნის მიმდინარე მინიმუმი

111
00:06:17,290 --> 00:06:20,030
ღირებულების i-th ინდექსი.

112
00:06:20,030 --> 00:06:23,160
ამიტომ პირველ iteration, ჩვენ ვაპირებთ
განიხილოს მინიმალური ღირებულება უნდა იყოს

113
00:06:23,160 --> 00:06:25,030
დაწყების ჩვენი მასივი.

114
00:06:25,030 --> 00:06:28,500
ამის შემდეგ, ჩვენ ვაპირებთ iterate მეტი
დარჩენილი მასივი, შემოწმების

115
00:06:28,500 --> 00:06:31,870
თუ არსებობს რაიმე ელემენტების ნაკლებია
ერთი, რომ ჩვენ ამჟამად

116
00:06:31,870 --> 00:06:33,900
გათვალისწინებით მინიმალური.

117
00:06:33,900 --> 00:06:38,840
>> ასე რომ აქ, ფასეულობები j პლუს ერთი - რომ
ნაკლებია, ვიდრე იმას, რასაც ჩვენ ამჟამად

118
00:06:38,840 --> 00:06:40,380
გათვალისწინებით მინიმალური.

119
00:06:40,380 --> 00:06:42,940
მაშინ ჩვენ ვაპირებთ განახლება რა
ჩვენ მიგვაჩნია, რომ მინიმუმ

120
00:06:42,940 --> 00:06:44,640
ინდექსი j პლუს 1.

121
00:06:44,640 --> 00:06:48,540
ასე რომ, რომ მთელ მასივი,
და შემდეგ ამ for loop, მინიმალური

122
00:06:48,540 --> 00:06:53,160
უნდა იყოს მინიმალური ელემენტს საწყისი
i-ე პოზიციაზე მასივი.

123
00:06:53,160 --> 00:06:57,350
>> მას შემდეგ, რაც ჩვენ, რომ ჩვენ შეგვიძლია სვოპ
მინიმალური ღირებულება შევიდა i-ე ადგილზეა

124
00:06:57,350 --> 00:06:58,230
მასივი.

125
00:06:58,230 --> 00:07:00,130
ასე რომ, ეს უბრალოდ სტანდარტული swap.

126
00:07:00,130 --> 00:07:03,940
ჩვენ ვინახავთ დროებით ღირებულება -
i-th ღირებულება მასივი -

127
00:07:03,940 --> 00:07:08,460
შევიდა i-th ღირებულება მასივი
მინიმალური ღირებულება, რომელიც ეკუთვნის იქ,

128
00:07:08,460 --> 00:07:13,580
და შემდეგ შესანახად ისევ სადაც
მიმდინარე მინიმალური ღირებულება გამოყენებული იქნება

129
00:07:13,580 --> 00:07:16,460
i-th ღირებულება მასივი, ასე რომ,
რომ ჩვენ არ დაკარგოს იგი.

130
00:07:16,460 --> 00:07:20,510
>> ასე, რომ გრძელდება
მომდევნო iteration.

131
00:07:20,510 --> 00:07:23,480
ჩვენ დავიწყებთ ეძებს მეორე
მინიმალური ღირებულება და ჩასვით რომ შევიდა

132
00:07:23,480 --> 00:07:24,590
მეორე ადგილი დაიკავეს.

133
00:07:24,590 --> 00:07:27,440
მესამე iteration, ჩვენ ვეძებთ
მესამე მინიმალური ღირებულება და insert

134
00:07:27,440 --> 00:07:31,550
რომ შევიდა მესამე ადგილზეა, და ა.შ.
სანამ ჩვენ დახარისხებული მასივი.

135
00:07:31,550 --> 00:07:33,820
ჩემი სახელი არის რობ, და ამ
იყო შერჩევის ჯიშია.

136
00:07:33,820 --> 00:07:39,456