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

2
00:00:13,300 --> 00:00:15,010
>> ROB BOWDEN: Γεια σου, είμαι 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
Θα μπορούσατε επίσης να εφαρμόσουν δυαδική αναζήτηση
επαναληπτικά, οπότε αν το έκανες αυτό,

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, η οποία
είναι η σειρά με την οποία είμαστε

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
Ελέγχουμε να δούμε αν η ισούται με 0, σε
ποια περίπτωση θα επιστρέψει false.

16
00:00:51,350 --> 00:00:54,770
Αυτό ακριβώς λέγοντας ότι αν έχουμε ένα άδειο
array, αξία δεν είναι σαφώς μια

17
00:00:54,770 --> 00:00:57,860
άδειο πίνακα, ώστε να μπορούμε να επιστρέφει false.

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
συστοιχία είναι το μεσαίο.

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
Έτσι, αυτό είναι ακριβώς αυτό που θέλουμε να
καθορίσετε μας ενημέρωση array - το αριστερό

52
00:02:50,120 --> 00:02:53,010
συστοιχία από το μεσαίο στοιχείο.

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
Έτσι, εάν σειρά μας ήταν μεγέθους n, τότε η
νέα σειρά θα είναι μεγέθους n μείον

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
>> Και πάλι, αν η συστοιχία ήταν μεγέθους 20 και
διαιρούμε με το 2 για να πάρει τη μέση,

60
00:03:18,710 --> 00:03:23,540
έτσι ώστε η μέση είναι 10, τότε η μέση μείον
πρόκειται να μας δώσει 10, οπότε 10

61
00:03:23,540 --> 00:03:25,330
στοιχεία προς τα δεξιά της μέσης.

62
00:03:25,330 --> 00:03:27,780
Αλλά έχουμε επίσης αυτό μείον
1, δεδομένου ότι δεν θέλουμε να

63
00:03:27,780 --> 00:03:29,700
περιλαμβάνει την ίδια την μέση.

64
00:03:29,700 --> 00:03:34,190
Έτσι, η μέση μείον μείον 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
Έτσι, εδώ, είμαστε περνώντας ένα
επικαιροποιημένες τιμές array.

68
00:03:46,180 --> 00:03:50,930
Αυτή η τιμή συν μεσαία συν 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
τιμές εμπορικό μέση συν 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
ότι θα νοιάζονται για το array
και το ανώτερο δείκτη που σας ενδιαφέρουν

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
Οπότε, ας πάρει αυτό διευθετηθεί.

89
00:05:12,220 --> 00:05:17,650
Τώρα, παρατηρούμε ότι το είδος είναι τα δύο τελευταία
παράμετροι int αξιών, η οποία είναι η

90
00:05:17,650 --> 00:05:21,110
πίνακα που είμαστε διαλογή, και 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 κ τετράγωνο.

94
00:05:26,690 --> 00:05:30,560
Θα μπορούσατε να επιλέξετε bubble sort, η επιλογή
είδος ή είδος εισαγωγής, ή

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
>> Έτσι, θα πάμε για να μετακινηθείτε
επί ολόκληρης της συστοιχίας.

98
00:05:40,030 --> 00:05:44,360
Λοιπόν, εδώ βλέπουμε ότι είμαστε επανάληψη
από 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
Στη συνέχεια, θα πάμε να πάει πέρα ​​από το σύνολο
της συστοιχίας και πάλι ψάχνει για το δεύτερο

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-οστό δείκτη.

112
00:06:20,030 --> 00:06:23,160
Έτσι, στην πρώτη επανάληψη, θα πάμε
να εξετάσει η ελάχιστη τιμή να είναι

113
00:06:23,160 --> 00:06:25,030
η έναρξη του πίνακα μας.

114
00:06:25,030 --> 00:06:28,500
Στη συνέχεια, θα πάμε για να μετακινηθείτε πάνω από το
υπόλοιπο της συστοιχίας, έλεγχο για να

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
Έτσι, κάνουν ότι σε ολόκληρο το φάσμα,
και μετά από αυτό για το βρόχο, το ελάχιστο

122
00:06:48,540 --> 00:06:53,160
θα πρέπει να είναι το ελάχιστο στοιχείο από
το i-th θέση στη συστοιχία.

123
00:06:53,160 --> 00:06:57,350
>> Μόλις έχουμε ότι, μπορούμε να ανταλλάξουν το
ελάχιστη τιμή στη θέση i-th

124
00:06:57,350 --> 00:06:58,230
στη συστοιχία.

125
00:06:58,230 --> 00:07:00,130
Έτσι, αυτό είναι απλά ένα πρότυπο ανταλλαγής.

126
00:07:00,130 --> 00:07:03,940
Εμείς αποθηκεύουν σε προσωρινή αξία -
το i-οστό τιμή στον πίνακα -

127
00:07:03,940 --> 00:07:08,460
μπει στο i-οστό τιμή στον πίνακα της
ελάχιστη τιμή που ανήκει εκεί,

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
>> Έτσι, αυτό συνεχίζει
την επόμενη επανάληψη.

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
Την τρίτη επανάληψη, θα αναζητήσουμε
η τρίτη ελάχιστη τιμή και το ένθετο

134
00:07:27,440 --> 00:07:31,550
ότι στην τρίτη θέση, και έτσι
στις μέχρι να έχουμε μια ταξινομημένη σειρά.

135
00:07:31,550 --> 00:07:33,820
Το όνομά μου είναι Rob, και αυτό
Ήταν ένα είδος επιλογής.

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