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
>> Το πρόγραμμα ΡΓΝϋ.Ο ζητά για τους αριθμούς
να γεμίσει το άχυρα, αναζητά η

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
Έτσι ΡΓΝϋ.Ο είναι γραμμένο ήδη.

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
false αν η τιμή είναι
όχι στα άχυρα.

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

21
00:01:11,610 --> 00:01:14,920
Αναζητήστε οποιαδήποτε λίστα που του έχουν ανατεθεί.

22
00:01:14,920 --> 00:01:21,190
Η δουλειά σου είναι να εφαρμόσει δυαδική αναζήτηση,
που έχει τρέξει χρόνο O του log n.

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
return 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