1
00:00:00,000 --> 00:00:03,346
>> [Παίζει μουσική]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Εντάξει.

4
00:00:06,220 --> 00:00:08,140
Έτσι δυαδική αναζήτηση είναι ένας
αλγόριθμο μπορούμε να χρησιμοποιήσουμε

5
00:00:08,140 --> 00:00:10,530
να βρει ένα στοιχείο εσωτερικό ενός πίνακα.

6
00:00:10,530 --> 00:00:14,710
Σε αντίθεση με τη γραμμική αναζήτηση, απαιτεί μια
του ειδικού όρου πρέπει να πληρούνται εκ των προτέρων,

7
00:00:14,710 --> 00:00:19,020
αλλά είναι πολύ πιο αποτελεσματική, αν
ότι η κατάσταση είναι, στην πραγματικότητα, συνάντησε.

8
00:00:19,020 --> 00:00:20,470
>> Έτσι ποια είναι η ιδέα εδώ;

9
00:00:20,470 --> 00:00:21,780
είναι διαίρει και βασίλευε.

10
00:00:21,780 --> 00:00:25,100
Θέλουμε να μειώσουμε το μέγεθος του
Η περιοχή αναζήτησης κατά το ήμισυ κάθε χρόνο

11
00:00:25,100 --> 00:00:27,240
Για να βρείτε έναν αριθμό-στόχο.

12
00:00:27,240 --> 00:00:29,520
Αυτό είναι όπου η κατάσταση
μπαίνει στο παιχνίδι, όμως.

13
00:00:29,520 --> 00:00:32,740
Μπορούμε να αξιοποιήσει μόνο τη δύναμη της
εξαλείφοντας ένα δεύτερο από τα στοιχεία

14
00:00:32,740 --> 00:00:36,070
χωρίς καν να κοιτάζει
τους αν η συστοιχία έχει διευθετηθεί.

15
00:00:36,070 --> 00:00:39,200
>> Αν είναι ένα πλήρες μίγμα επάνω,
Δεν μπορούμε απλά να βγει από το χέρι

16
00:00:39,200 --> 00:00:42,870
απορρίψει ένα δεύτερο από τα στοιχεία, επειδή
δεν ξέρουμε τι είμαστε απόρριψη.

17
00:00:42,870 --> 00:00:45,624
Αλλά αν η συστοιχία είναι ταξινομημένη,
μπορούμε να το κάνουμε αυτό, γιατί εμείς

18
00:00:45,624 --> 00:00:48,040
γνωρίζουμε ότι τα πάντα για να το
αριστερά, όπου βρισκόμαστε τώρα

19
00:00:48,040 --> 00:00:50,500
πρέπει να είναι μικρότερη από ό, τι η
τιμή είμαστε σήμερα σε.

20
00:00:50,500 --> 00:00:52,300
Και τα πάντα για να το
δεξιά από εκεί που είμαστε

21
00:00:52,300 --> 00:00:55,040
θα πρέπει να είναι μεγαλύτερη από την τιμή
Αυτήν τη στιγμή εξετάζουμε.

22
00:00:55,040 --> 00:00:58,710
>> Έτσι ποια είναι η ψευδοκώδικα
βήματα για την δυαδική αναζήτηση;

23
00:00:58,710 --> 00:01:02,310
Επαναλαμβάνουμε τη διαδικασία μέχρι το
συστοιχία ή, καθώς προχωράμε μέσα,

24
00:01:02,310 --> 00:01:07,740
υπο συστοιχίες, μικρότερα κομμάτια
η αρχική διάταξη, είναι μεγέθους 0.

25
00:01:07,740 --> 00:01:10,960
Υπολογίστε το μέσο
της τρέχουσας υπο-συστοιχία.

26
00:01:10,960 --> 00:01:14,460
>> Αν η τιμή που ψάχνετε είναι
στο εν λόγω στοιχείο του πίνακα, να σταματήσει.

27
00:01:14,460 --> 00:01:15,030
Το βρηκες.

28
00:01:15,030 --> 00:01:16,550
Αυτό είναι υπέροχο.

29
00:01:16,550 --> 00:01:19,610
Διαφορετικά, αν ο στόχος είναι
λιγότερο από ό, τι είναι στη μέση,

30
00:01:19,610 --> 00:01:23,430
Έτσι, αν η τιμή που ψάχνουμε
είναι χαμηλότερο από αυτό που βλέπουμε,

31
00:01:23,430 --> 00:01:26,780
επαναλάβετε αυτή τη διαδικασία και πάλι, αλλά
αλλάξετε το τελικό σημείο, αντί

32
00:01:26,780 --> 00:01:29,300
να είναι η αρχική
ολοκληρώσει την πλήρη σειρά,

33
00:01:29,300 --> 00:01:34,110
να είναι μόνο προς τα αριστερά
όπου εμείς απλά κοίταξε.

34
00:01:34,110 --> 00:01:38,940
>> Γνωρίζαμε ότι η μέση ήταν πολύ υψηλό,
ή ο στόχος ήταν μικρότερη από την μέση,

35
00:01:38,940 --> 00:01:42,210
και έτσι πρέπει να υπάρχει, εάν
υπάρχει καθόλου στη συστοιχία,

36
00:01:42,210 --> 00:01:44,660
κάπου στα αριστερά του κέντρου.

37
00:01:44,660 --> 00:01:48,120
Και έτσι θα ρυθμίσετε το πίνακα
τοποθεσία ακριβώς στα αριστερά

38
00:01:48,120 --> 00:01:51,145
του μέσο ως το νέο τελικό σημείο.

39
00:01:51,145 --> 00:01:53,770
Αντίθετα, αν ο στόχος είναι
μεγαλύτερη από ό, τι είναι στη μέση,

40
00:01:53,770 --> 00:01:55,750
κάνουμε ακριβώς το ίδιο
διαδικασία, αλλά αντ 'αυτού

41
00:01:55,750 --> 00:01:59,520
αλλάξετε το σημείο εκκίνησης για να
ακριβώς στα δεξιά του μεσαίου σημείου

42
00:01:59,520 --> 00:02:00,680
εμείς απλά υπολογίζεται.

43
00:02:00,680 --> 00:02:03,220
Και τότε, θα αρχίσει και πάλι τη διαδικασία.

44
00:02:03,220 --> 00:02:05,220
>> Ας απεικονίσει αυτό, εντάξει;

45
00:02:05,220 --> 00:02:08,620
Έτσι, υπάρχει μια παρτίδα σε εξέλιξη και εδώ,
αλλά εδώ είναι μια σειρά από 15 στοιχεία.

46
00:02:08,620 --> 00:02:11,400
Και θα πάμε να την παρακολούθηση
από πολλά περισσότερα πράγματα αυτή τη φορά.

47
00:02:11,400 --> 00:02:13,870
Έτσι, σε γραμμική αναζήτηση, ήμασταν
απλά φροντίζοντας για έναν στόχο.

48
00:02:13,870 --> 00:02:15,869
Αλλά αυτή τη φορά θέλουμε να
νοιάζονται για πού είμαστε

49
00:02:15,869 --> 00:02:18,480
αρχίζει να φαίνεται, όπου
Τα έχουμε διακοπή αναζητούν,

50
00:02:18,480 --> 00:02:21,876
και ποιο είναι το μέσον
της τρέχουσας σειράς.

51
00:02:21,876 --> 00:02:23,250
Έτσι, εδώ πάμε με δυαδική αναζήτηση.

52
00:02:23,250 --> 00:02:25,290
Είμαστε λίγο πολύ καλό να πάει, έτσι δεν είναι;

53
00:02:25,290 --> 00:02:28,650
Είμαι ακριβώς πρόκειται να βάλει κάτω
κάτω από εδώ ένα σύνολο δεικτών.

54
00:02:28,650 --> 00:02:32,430
Αυτό είναι βασικά ακριβώς τι στοιχείο
της συστοιχίας μιλάμε.

55
00:02:32,430 --> 00:02:34,500
Με γραμμική αναζήτηση, εμείς
φροντίδα, στο μέτρο που εμείς

56
00:02:34,500 --> 00:02:36,800
Πρέπει να γνωρίζουμε πόσοι
στοιχεία είμαστε επανάληψη πάνω,

57
00:02:36,800 --> 00:02:40,010
αλλά στην πραγματικότητα δεν με νοιάζει τι
στοιχείο Αυτήν τη στιγμή εξετάζουμε.

58
00:02:40,010 --> 00:02:41,014
Σε δυαδική αναζήτηση, το κάνουμε.

59
00:02:41,014 --> 00:02:42,930
Και έτσι αυτά είναι μόνο
εκεί σαν ένα μικρό οδηγό.

60
00:02:42,930 --> 00:02:44,910
>> Έτσι, μπορούμε να αρχίσουμε, έτσι δεν είναι;

61
00:02:44,910 --> 00:02:46,240
Λοιπόν, δεν είναι αρκετά.

62
00:02:46,240 --> 00:02:48,160
Θυμηθείτε τι είπα
σχετικά με δυαδική αναζήτηση;

63
00:02:48,160 --> 00:02:50,955
Εμείς δεν μπορούμε να το κάνουμε σε ένα
αδιαχώριστα συστοιχία ή αλλιώς,

64
00:02:50,955 --> 00:02:55,820
Δεν εγγυόμαστε ότι η
ορισμένα στοιχεία ή αξίες δεν είναι

65
00:02:55,820 --> 00:02:57,650
είναι λάθος
απορρίπτεται όταν εμείς απλά

66
00:02:57,650 --> 00:02:59,920
αποφασίσει να αγνοήσει ένα δεύτερο της συστοιχίας.

67
00:02:59,920 --> 00:03:02,574
>> Έτσι βήμα ένα με δυαδική αναζήτηση
είναι πρέπει να έχετε ένα ταξινομημένο πίνακα.

68
00:03:02,574 --> 00:03:05,240
Και μπορείτε να χρησιμοποιήσετε οποιοδήποτε από τα διαλογής
αλγόριθμοι έχουμε μιλήσει για

69
00:03:05,240 --> 00:03:06,700
για να μπορείτε να πάρετε σε αυτή τη θέση.

70
00:03:06,700 --> 00:03:10,370
Έτσι τώρα, είμαστε σε μια θέση όπου
μπορούμε να εκτελέσουμε δυαδική αναζήτηση.

71
00:03:10,370 --> 00:03:12,560
>> Ας επαναλάβετε τη διαδικασία
βήμα προς βήμα και να κρατήσει

72
00:03:12,560 --> 00:03:14,830
παρακολουθείτε τι συμβαίνει, όπως πάμε.

73
00:03:14,830 --> 00:03:17,980
Έτσι, το πρώτο που πρέπει να κάνουμε είναι να υπολογίσει
το μέσο της τρέχουσας σειράς.

74
00:03:17,980 --> 00:03:20,620
Λοιπόν, θα έλεγα ότι είμαστε, πρώτα απ '
όλα, ψάχνει για την τιμή 19.

75
00:03:20,620 --> 00:03:22,290
Προσπαθούμε να βρούμε τον αριθμό 19.

76
00:03:22,290 --> 00:03:25,380
Το πρώτο στοιχείο του παρόντος
συστοιχία βρίσκεται στο ευρετήριο μηδέν,

77
00:03:25,380 --> 00:03:28,880
και το τελευταίο στοιχείο της παρούσας
συστοιχία βρίσκεται σε δείκτη 14.

78
00:03:28,880 --> 00:03:31,430
Και έτσι θα ονομάζουμε εκείνα έναρξης και λήξης.

79
00:03:31,430 --> 00:03:35,387
>> Έτσι υπολογίζουμε το μέσο κατά
προσθέτοντας 0 συν 14 διαιρείται δια 2?

80
00:03:35,387 --> 00:03:36,720
αρκετά απλή μέσο.

81
00:03:36,720 --> 00:03:40,190
Και μπορούμε να πούμε ότι
το κεντρικό σημείο είναι τώρα 7.

82
00:03:40,190 --> 00:03:43,370
Έτσι είναι 15 αυτό που ψάχνετε;

83
00:03:43,370 --> 00:03:43,940
Όχι δεν είναι.

84
00:03:43,940 --> 00:03:45,270
Ψάχνουμε για 19.

85
00:03:45,270 --> 00:03:49,400
Αλλά γνωρίζουμε ότι το 19 είναι μεγαλύτερο
από ό, τι βρήκαμε στη μέση.

86
00:03:49,400 --> 00:03:52,470
>> Έτσι, αυτό που μπορούμε να κάνουμε είναι
αλλάξετε το σημείο εκκίνησης

87
00:03:52,470 --> 00:03:57,280
να είναι ακριβώς στα δεξιά του
μέσο, ​​και επαναλάβετε τη διαδικασία.

88
00:03:57,280 --> 00:04:01,690
Και όταν το κάνουμε αυτό, λέμε τώρα η
νέο σημείο εκκίνησης είναι η θέση πίνακα 8.

89
00:04:01,690 --> 00:04:07,220
Αυτό που κάναμε είναι αποτελεσματικά
αγνοείται πάντα στα αριστερά του 15.

90
00:04:07,220 --> 00:04:09,570
Έχουμε εξαλειφθεί το ήμισυ
του προβλήματος, και τώρα,

91
00:04:09,570 --> 00:04:13,510
αντί να χρειάζεται να αναζητήσετε
πάνω από 15 στοιχεία σε σειρά μας,

92
00:04:13,510 --> 00:04:15,610
δεν έχουμε παρά να αναζητήσετε πάνω από 7.

93
00:04:15,610 --> 00:04:17,706
Έτσι 8 είναι το νέο σημείο εκκίνησης.

94
00:04:17,706 --> 00:04:19,600
14 εξακολουθεί να είναι το τελικό σημείο.

95
00:04:19,600 --> 00:04:21,430
>> Και τώρα, θα πάει πάνω από αυτό και πάλι.

96
00:04:21,430 --> 00:04:22,810
Υπολογίζουμε το νέο μέσο.

97
00:04:22,810 --> 00:04:27,130
8 συν 14 είναι 22, διαιρείται δια 2 είναι 11.

98
00:04:27,130 --> 00:04:28,660
Είναι αυτό που ψάχνετε;

99
00:04:28,660 --> 00:04:30,110
Όχι δεν είναι.

100
00:04:30,110 --> 00:04:32,930
Ψάχνουμε για μια τιμή που είναι
λιγότερο από αυτό που μόλις βρήκα.

101
00:04:32,930 --> 00:04:34,721
Έτσι θα πάμε να επαναλάβουμε
η διαδικασία και πάλι.

102
00:04:34,721 --> 00:04:38,280
Εμείς πάμε για να αλλάξετε το τελικό σημείο για να
είναι ακριβώς στα αριστερά του κέντρου.

103
00:04:38,280 --> 00:04:41,800
Έτσι, το νέο τελικό σημείο γίνεται 10.

104
00:04:41,800 --> 00:04:44,780
Και τώρα, αυτό είναι το μόνο μέρος του
η διάταξη θα πρέπει να ταξινομήσετε μέσω.

105
00:04:44,780 --> 00:04:48,460
Έτσι έχουμε πλέον εξαλειφθεί
12 από τα 15 στοιχεία.

106
00:04:48,460 --> 00:04:51,550
Ξέρουμε ότι αν 19
υπάρχει στη συστοιχία, το

107
00:04:51,550 --> 00:04:57,210
πρέπει να υπάρχει κάπου μεταξύ του στοιχείου
αριθμός 8 και το στοιχείο τον αριθμό 10.

108
00:04:57,210 --> 00:04:59,400
>> Γι 'αυτό και υπολογίζει ξανά το νέο μέσο.

109
00:04:59,400 --> 00:05:02,900
8 συν 10 είναι 18, διαιρείται με 2 9.

110
00:05:02,900 --> 00:05:05,074
Και σε αυτή την περίπτωση, κοιτάξτε, η
στόχος είναι στη μέση.

111
00:05:05,074 --> 00:05:06,740
Βρήκαμε αυτό ακριβώς που ψάχνετε.

112
00:05:06,740 --> 00:05:07,780
Μπορούμε να σταματήσουμε.

113
00:05:07,780 --> 00:05:10,561
Έχουμε ολοκληρώσει επιτυχώς
μια δυαδική αναζήτηση.

114
00:05:10,561 --> 00:05:11,060
Εντάξει.

115
00:05:11,060 --> 00:05:13,930
Γνωρίζουμε, λοιπόν, αυτόν τον αλγόριθμο
λειτουργεί αν ο στόχος είναι

116
00:05:13,930 --> 00:05:16,070
κάπου μέσα της συστοιχίας.

117
00:05:16,070 --> 00:05:19,060
Μήπως αυτό το έργο, αν ο αλγόριθμος
ο στόχος δεν είναι στη συστοιχία;

118
00:05:19,060 --> 00:05:20,810
Λοιπόν, ας αρχίσει
πάλι, και αυτή τη φορά,

119
00:05:20,810 --> 00:05:23,380
ας ρίξουμε μια ματιά για το στοιχείο
16, το οποίο οπτικά μπορούμε να δούμε

120
00:05:23,380 --> 00:05:25,620
δεν υπάρχει πουθενά στη συστοιχία.

121
00:05:25,620 --> 00:05:27,110
>> Το σημείο εκκίνησης είναι και πάλι 0.

122
00:05:27,110 --> 00:05:28,590
Το τελικό σημείο είναι και πάλι 14.

123
00:05:28,590 --> 00:05:32,490
Αυτοί είναι οι δείκτες του πρώτου και του
τελευταία στοιχεία της πλήρη σειρά.

124
00:05:32,490 --> 00:05:36,057
Και θα περάσουν από τη διαδικασία που μόλις
πέρασε και πάλι, προσπαθώντας να βρει 16,

125
00:05:36,057 --> 00:05:39,140
ακόμη και αν οπτικά, μπορούμε ήδη να
λένε ότι δεν πρόκειται να είναι εκεί.

126
00:05:39,140 --> 00:05:43,450
Εμείς απλά θέλουμε να βεβαιωθείτε ότι αυτό το αλγόριθμο
θα, στην πραγματικότητα, εξακολουθούν να εργάζονται σε κάποιο τρόπο

127
00:05:43,450 --> 00:05:46,310
και όχι απλά να μας αφήσετε
κολλήσει σε ένα άπειρο βρόχο.

128
00:05:46,310 --> 00:05:48,190
>> Ποιο είναι λοιπόν το πρώτο βήμα;

129
00:05:48,190 --> 00:05:50,230
Υπολογίστε το μέσο
της τρέχουσας σειράς.

130
00:05:50,230 --> 00:05:52,790
Ποιο είναι το μέσο
του ισχύοντος πίνακα;

131
00:05:52,790 --> 00:05:54,410
Λοιπόν, αυτό είναι 7, έτσι δεν είναι;

132
00:05:54,410 --> 00:05:57,560
14 συν 0 διαιρείται με 2 είναι 7.

133
00:05:57,560 --> 00:05:59,280
Είναι 15 αυτό που ψάχνετε;

134
00:05:59,280 --> 00:05:59,780
Κανένα.

135
00:05:59,780 --> 00:06:02,930
Είναι αρκετά κοντά, αλλά ψάχνουμε
για μια τιμή λίγο μεγαλύτερη από εκείνη.

136
00:06:02,930 --> 00:06:06,310
>> Έτσι, γνωρίζουμε ότι πρόκειται να
είναι πουθενά στα αριστερά του 15.

137
00:06:06,310 --> 00:06:08,540
Ο στόχος είναι μεγαλύτερη από
τι είναι στο μέσον.

138
00:06:08,540 --> 00:06:12,450
Και έτσι θέσαμε το νέο σημείο εκκίνησης για την
να είναι ακριβώς στα δεξιά της μεσαίας.

139
00:06:12,450 --> 00:06:16,130
Το μέσον είναι σήμερα 7, έτσι
ας πούμε το νέο σημείο εκκίνησης είναι 8.

140
00:06:16,130 --> 00:06:18,130
Και τι έχουμε πραγματικά
γίνεται και πάλι αγνοείται

141
00:06:18,130 --> 00:06:21,150
ολόκληρο το αριστερό μισό της συστοιχίας.

142
00:06:21,150 --> 00:06:23,750
>> Τώρα, επαναλαμβάνουμε το
επεξεργάζονται ακόμα μία φορά.

143
00:06:23,750 --> 00:06:24,910
Υπολογίστε το νέο μέσο.

144
00:06:24,910 --> 00:06:29,350
8 συν 14 είναι 22, διαιρείται δια 2 είναι 11.

145
00:06:29,350 --> 00:06:31,060
Είναι 23 αυτό που ψάχνετε;

146
00:06:31,060 --> 00:06:31,870
Δυστηχώς ΟΧΙ.

147
00:06:31,870 --> 00:06:34,930
Ψάχνουμε για μια τιμή
ότι είναι μικρότερη από 23.

148
00:06:34,930 --> 00:06:37,850
Και στην προκειμένη περίπτωση, θα πάμε
για να αλλάξετε το τελικό σημείο για να είναι ακριβώς

149
00:06:37,850 --> 00:06:40,035
στα αριστερά του τρέχοντος μέσο.

150
00:06:40,035 --> 00:06:43,440
Η τρέχουσα μέσον είναι 11, και
έτσι θα θέσει το νέο τελικό σημείο

151
00:06:43,440 --> 00:06:46,980
για την επόμενη φορά που θα πάμε
μέσω αυτής της διαδικασίας για 10.

152
00:06:46,980 --> 00:06:48,660
>> Και πάλι, θα περάσουν από τη διαδικασία πάλι.

153
00:06:48,660 --> 00:06:49,640
Υπολογίστε το μέσο.

154
00:06:49,640 --> 00:06:53,100
8 συν 10 διαιρείται δια 2 είναι 9.

155
00:06:53,100 --> 00:06:54,750
Είναι 19 αυτό που ψάχνετε;

156
00:06:54,750 --> 00:06:55,500
Δυστηχώς ΟΧΙ.

157
00:06:55,500 --> 00:06:58,050
Είμαστε ακόμα ψάχνει για
ένας αριθμός μικρότερος από αυτό.

158
00:06:58,050 --> 00:07:02,060
Έτσι θα αλλάξουν το τελικό σημείο αυτή τη φορά
να είναι ακριβώς στα αριστερά του κέντρου.

159
00:07:02,060 --> 00:07:05,532
Η μέση τιμή είναι σήμερα 9,
έτσι ώστε το τελικό σημείο θα είναι 8.

160
00:07:05,532 --> 00:07:07,920
Και τώρα, είμαστε ακριβώς ψάχνετε
σε μια ενιαία συστοιχία στοιχείο.

161
00:07:07,920 --> 00:07:10,250
>> Ποιο είναι το μέσο αυτής της διάταξης;

162
00:07:10,250 --> 00:07:13,459
Λοιπόν, ξεκινά στις 8, το
τελειώνει στις 8, το κεντρικό σημείο είναι 8.

163
00:07:13,459 --> 00:07:14,750
Είναι ότι αυτό που ψάχνετε;

164
00:07:14,750 --> 00:07:16,339
Ψάχνουμε για 17;

165
00:07:16,339 --> 00:07:17,380
Όχι, ψάχνουμε για 16.

166
00:07:17,380 --> 00:07:20,160
Έτσι, αν υπάρχει στη συστοιχία,
θα πρέπει να υπάρχει κάπου

167
00:07:20,160 --> 00:07:21,935
στα αριστερά του όπου βρισκόμαστε τώρα.

168
00:07:21,935 --> 00:07:23,060
Λοιπόν, τι θα κάνουμε;

169
00:07:23,060 --> 00:07:26,610
Λοιπόν, θα ορίσετε το σημείο τέλους για να είναι ακριβώς
στα αριστερά του τρέχοντος μέσο.

170
00:07:26,610 --> 00:07:29,055
Έτσι θα αλλάξουν το τελικό σημείο 7.

171
00:07:29,055 --> 00:07:32,120
Βλέπετε τι ακριβώς
συνέβη εδώ, όμως;

172
00:07:32,120 --> 00:07:33,370
Αναζητήστε εδώ τώρα.

173
00:07:33,370 --> 00:07:35,970
>> Ξεκινήστε τώρα είναι μεγαλύτερη από ό, τι τέλος.

174
00:07:35,970 --> 00:07:39,620
Αποτελεσματικά, τα δύο άκρα
της σειράς μας έχουν περάσει,

175
00:07:39,620 --> 00:07:42,252
και το σημείο έναρξης είναι
Τώρα, μετά το τελικό σημείο.

176
00:07:42,252 --> 00:07:43,960
Λοιπόν, αυτό δεν
κανένα νόημα, έτσι δεν είναι;

177
00:07:43,960 --> 00:07:47,960
Μέχρι τώρα, αυτό που μπορούμε να πούμε είναι ότι
έχουν μια υπο-συστοιχία μεγέθους 0.

178
00:07:47,960 --> 00:07:50,110
Και μόλις είμαστε φτάσει σε
αυτό το σημείο, μπορούμε τώρα

179
00:07:50,110 --> 00:07:53,940
εγγυηθεί ότι το στοιχείο 16
δεν υπάρχει στη συστοιχία,

180
00:07:53,940 --> 00:07:56,280
Επειδή το σημείο εκκίνησης
και του τελικού σημείου έχουν διασχίσει.

181
00:07:56,280 --> 00:07:58,340
Και έτσι δεν είναι εκεί.

182
00:07:58,340 --> 00:08:01,340
Τώρα, παρατηρούμε ότι αυτό είναι ελαφρώς
διαφορετικό από το σημείο έναρξης και λήξης

183
00:08:01,340 --> 00:08:02,900
σημείο είναι το ίδιο.

184
00:08:02,900 --> 00:08:05,030
Εάν ήμασταν που αναζητούν
για 17, θα πρέπει

185
00:08:05,030 --> 00:08:08,870
ήταν στη συστοιχία, και το σημείο εκκίνησης
και τελικό σημείο του εν λόγω τελευταία επανάληψη

186
00:08:08,870 --> 00:08:11,820
πριν διασχίσει αυτά τα σημεία,
θα είχαμε βρεθεί εκεί 17.

187
00:08:11,820 --> 00:08:15,510
Είναι μόνο όταν διασχίζουν ότι μπορούμε
εγγυάται ότι το στοιχείο δεν

188
00:08:15,510 --> 00:08:17,180
υπάρχουν στη συστοιχία.

189
00:08:17,180 --> 00:08:20,260
>> Έτσι, ας ρίξουμε μια πολύ λιγότερα
βήματα από τη γραμμική αναζήτηση.

190
00:08:20,260 --> 00:08:23,250
Στη χειρότερη περίπτωση, θα έπρεπε
να χωρίσουν μια λίστα με n στοιχεία

191
00:08:23,250 --> 00:08:27,770
επανειλημμένα κατά το ήμισυ για να βρουν το στόχο,
είτε επειδή το στοιχείο στόχος

192
00:08:27,770 --> 00:08:33,110
θα είναι κάπου στην τελευταία
διαίρεση, ή δεν υπάρχει καθόλου.

193
00:08:33,110 --> 00:08:37,830
Έτσι, στη χειρότερη περίπτωση, θα πρέπει να
χωρίσουν οι array-- ξέρεις;

194
00:08:37,830 --> 00:08:40,510
Είσοδος φορές ν? εμείς
πρέπει να κοπεί το πρόβλημα

195
00:08:40,510 --> 00:08:42,610
σε ένα δεύτερο ορισμένο αριθμό φορών.

196
00:08:42,610 --> 00:08:45,160
Αυτό πολλές φορές είναι log n.

197
00:08:45,160 --> 00:08:46,510
>> Ποιο είναι το καλύτερο σενάριο;

198
00:08:46,510 --> 00:08:48,899
Λοιπόν, η πρώτη φορά που
υπολογίζει το μέσο,

199
00:08:48,899 --> 00:08:50,190
θα βρείτε αυτό που ψάχνετε.

200
00:08:50,190 --> 00:08:52,150
Σε όλες τις προηγούμενες
παραδείγματα στη δυαδική αναζήτηση

201
00:08:52,150 --> 00:08:55,489
έχουμε μόλις περάσει πάνω, αν είχαμε
ψάξει για το στοιχείο 15,

202
00:08:55,489 --> 00:08:57,030
θα έχουν διαπιστώσει ότι αμέσως.

203
00:08:57,030 --> 00:08:58,321
Αυτός ήταν στην αρχή.

204
00:08:58,321 --> 00:09:01,200
Αυτό ήταν το κεντρικό σημείο του
Η πρώτη προσπάθεια σε ένα split

205
00:09:01,200 --> 00:09:03,950
ενός τμήματος σε δυαδική αναζήτηση.

206
00:09:03,950 --> 00:09:06,350
>> Και έτσι στη χειρότερη
περίπτωση, δυαδική αναζήτηση τρέχει

207
00:09:06,350 --> 00:09:11,580
σε log n, η οποία είναι σημαντικά καλύτερη
από τη γραμμική αναζήτηση, στη χειρότερη περίπτωση.

208
00:09:11,580 --> 00:09:16,210
Στην καλύτερη περίπτωση, τα δυαδικά
αναζήτηση τρέχει σε ωμέγα-1.

209
00:09:16,210 --> 00:09:18,990
Έτσι δυαδική αναζήτηση είναι πολύ
καλύτερα από ό, τι με τη γραμμική αναζήτηση,

210
00:09:18,990 --> 00:09:23,270
αλλά θα πρέπει να ασχοληθεί με τη διαδικασία του
διαλογή σειρά σας για να μπορέσετε να

211
00:09:23,270 --> 00:09:26,140
αξιοποιούν τη δύναμη της δυαδικής αναζήτησης.

212
00:09:26,140 --> 00:09:27,130
>> Είμαι ο Νταγκ Lloyd.

213
00:09:27,130 --> 00:09:29,470
Αυτό είναι το CS 50.

214
00:09:29,470 --> 00:09:31,070