[RIPRODUZIONE DI BRANI MUSICALI] 

DOUG LLOYD: Va bene. Quindi ricerca binaria è un algoritmo possiamo usare trovare un elemento all'interno di una matrice. Diversamente ricerca lineare, richiede un condizione particolare essere soddisfatta in anticipo, ma è così molto più efficiente se tale condizione, infatti, incontrato. 

Allora, qual è l'idea qui? è divide et impera. Vogliamo ridurre le dimensioni di l'area di ricerca della metà ogni volta al fine di trovare un numero di destinazione. È qui che tale condizione entra in gioco, però. Possiamo solo sfruttare la potenza di eliminando metà degli elementi senza neanche guardare loro se l'array vengono ordinati. 

Se si tratta di un mix completo up, non possiamo solo di mano scartare metà degli elementi, perché non sappiamo cosa stiamo scartando. Ma se l'array è ordinato, possiamo farlo, perché noi sapere che tutto il sinistra di dove ci troviamo attualmente deve essere inferiore alla valore che siamo attualmente a. E tutto al destra di dove siamo deve essere maggiore del valore al momento stiamo guardando. 

Allora qual è il pseudocodice passi per la ricerca binaria? Ripetiamo questo processo fino a quando la array o, come si procede attraverso, array sub, piccoli pezzi di la matrice originale, è di dimensioni 0. Calcolare il punto medio dell'array sottopagina corrente. 

Se il valore che stai cercando è in tale elemento dell'array, stop. L'hai trovato. È fantastico. Altrimenti, se il bersaglio è meno di ciò che è al centro, così se il valore che stiamo cercando per è inferiore a quello che si vede, ripetere questo processo, ma modificare il punto finale, invece di essere l'originale completare gamma completa, essere appena a sinistra di cui abbiamo appena guardato. 

Sapevamo che il mezzo era troppo alto, o l'obiettivo era meno di mezzo, e quindi deve esistere, se esiste affatto nella matrice, posto alla sinistra del punto medio. E così imposteremo l'array posizione appena a sinistra del punto medio come nuovo punto finale. Viceversa, se il bersaglio è maggiore di quello che è in mezzo, noi facciamo la stessa esatta processo, ma invece abbiamo modificare il punto iniziale di essere subito a destra del punto medio abbiamo appena calcolato. E poi, si comincia di nuovo il processo. 

Cerchiamo di visualizzare questo, OK? Quindi c'è un sacco di cose e qui, ma qui è un array dei 15 elementi. E stiamo andando a tenere traccia di molte più cose questa volta. Quindi, in ricerca lineare, eravamo solo preoccuparsi di un bersaglio. Ma questa volta vogliamo preoccupano dove siamo cominciando a guardare, dove ci fermiamo alla ricerca, e qual è il punto medio dell'array corrente. Quindi qui si va con ricerca binaria. Siamo più o meno bene ad andare, giusto? Sto solo andando a mettere giù sotto qui un insieme di indici. Questo è fondamentalmente solo quale elemento della matrice di cui stiamo parlando. Con ricerca lineare, abbiamo cura, in quanto ci bisogno di sapere quanti Elementi stiamo iterare su, ma in realtà non importa cosa elemento momento stiamo guardando. Alla ricerca binaria, che facciamo. E così questi sono solo lì come una piccola guida. 

Così possiamo iniziare, giusto? Beh, non proprio. Ricordate ciò che ho detto su ricerca binaria? Non possiamo farlo su un matrice indifferenziati oppure, non stiamo garantendo che il alcuni elementi o valori non sono accidentale scartato quando abbiamo appena decidere di ignorare metà dell'array. 

Così passo uno con ricerca binaria è devi avere un array ordinato. Ed è possibile utilizzare uno dei smistamento algoritmi di cui abbiamo parlato per arrivare a quella posizione. Così ora, siamo in una posizione in cui possiamo eseguire la ricerca binaria. 

Quindi cerchiamo di ripetere il processo passo dopo passo e mantenere traccia di quello che sta accadendo, come andiamo. Quindi la prima abbiamo bisogno di fare è calcolare il punto medio della matrice corrente. Bene, diremo che siamo, prima di tutto, alla ricerca per il valore 19. Stiamo cercando di trovare il numero 19. Il primo elemento di questo matrice si trova a indice zero, e l'ultimo elemento di questa matrice si trova a 14 dell'indice. E così chiameremo quelle di inizio e fine. 

Così si calcola il punto medio per aggiungendo 0 plus 14 diviso 2; punto medio abbastanza semplice. E possiamo dire che il punto medio è ora 7. Quindi è 15 quello che stiamo cercando? No non lo è. Stiamo cercando 19. Ma noi sappiamo che il 19 è maggiore di quello che abbiamo trovato al centro. 

Che cosa possiamo fare è modificare il punto iniziale essere appena a destra della punto medio, e ripetere il processo. E quando lo facciamo, ora diciamo la nuovo punto di partenza è la posizione di matrice 8. Quello che abbiamo fatto è efficace ignorato tutto a sinistra di 15. Abbiamo eliminato la metà del problema, e ora, invece di dover cercare oltre 15 elementi nella nostra gamma, non ci resta che cercare su 7. Quindi 8 è il nuovo punto di partenza. 14 è ancora il punto finale. 

E adesso, andiamo su questo nuovo. Calcoliamo il nuovo punto medio. 8 plus 14 è 22, diviso 2 è 11. È questo ciò che stiamo cercando? No non lo è. Siamo alla ricerca di un valore che è meno di quello che abbiamo appena trovato. Così stiamo andando a ripetere il processo di nuovo. Stiamo andando a cambiare il punto finale essere appena a sinistra del punto medio. Così il nuovo punto finale diventa 10. E ora, questa è l'unica parte di l'array dobbiamo ordinare attraverso. Così ora abbiamo eliminato 12 dei 15 elementi. Sappiamo che se 19 esiste nella matrice, esso deve esistere da qualche parte tra elemento numero 8 e l'elemento numero 10. 

Così si calcola di nuovo il nuovo punto medio. 8 più 10 è 18, diviso 2 è 9. E in questo caso, guarda, la bersaglio è al centro. Abbiamo trovato esattamente quello che stiamo cercando. Possiamo fermarci. Abbiamo completato con successo una ricerca binaria. Tutto ok. Così sappiamo questo algoritmo funziona se l'obiettivo è qualche parte all'interno della matrice. Fa questo lavoro algoritmo se il bersaglio non è nell'array? Bene, cominciamo esso di nuovo, e questa volta, diamo un'occhiata per l'elemento 16, che visivamente si vede non esiste nessuna parte nella matrice. 

Il punto di partenza è di nuovo 0. Il punto finale è di nuovo 14. Questi sono gli indici della prima e ultimi elementi della matrice completa. E andremo attraverso il processo che abbiamo appena ha attraversato di nuovo, cercando di trovare 16, anche se visivamente, possiamo già dire che non sarà lì. Vogliamo solo per assicurarsi che questo algoritmo sarà, infatti, ancora funzionare in qualche modo e non appena ci lascia bloccato in un ciclo infinito. 

Allora qual è il passo prima? Calcolare il punto medio dell'array corrente. Qual è il punto medio della matrice corrente? Beh, è ​​il 7, giusto? 14 più 0 diviso 2 è 7. È 15 quello che stiamo cercando? No. E 'abbastanza vicino, ma stiamo cercando per un valore leggermente più grande di quello. 

Così sappiamo che sta andando a in nessun posto a fianco di 15. L'obiettivo è superiore cosa c'è nel punto medio. E così abbiamo impostato il nuovo punto di partenza per essere appena a destra del centro. Il punto medio è attualmente 7, così diciamo che il nuovo punto di partenza è di 8. E quello che abbiamo in modo efficace fatto di nuovo viene ignorato tutta la metà sinistra della matrice. 

Ora, ripetiamo la elaborare ancora una volta. Calcolare il nuovo punto medio. 8 plus 14 è 22, diviso 2 è 11. È 23 quello che stiamo cercando? Sfortunatamente no. Stiamo cercando per un valore questo è inferiore a 23. E così in questo caso, stiamo andando per modificare il punto finale di essere solo alla sinistra del punto medio corrente. Il punto medio attuale è 11, e quindi imposteremo il nuovo punto finale per la prossima volta che andiamo attraverso questo processo a 10. 

Ancora una volta, passiamo attraverso il processo di nuovo. Calcolare il punto medio. 8 più 10 diviso 2 è 9. È 19 quello che stiamo cercando? Sfortunatamente no. Stiamo ancora cercando un numero inferiore a quello. Così cambieremo il punto finale questa volta essere appena a sinistra del punto medio. Il punto centrale è attualmente 9, quindi il punto finale sarà 8. E ora, stiamo solo cercando in un singolo array elemento. 

Qual è il punto centrale di questo array? Ebbene, inizia alle 8, essa termina a 8, il punto medio è 8. E 'questo che stiamo cercando? Stiamo cercando 17? No, stiamo cercando 16. Quindi, se esiste nella matrice, deve esistere da qualche parte a sinistra di dove ci troviamo attualmente. Allora cosa dobbiamo fare? Beh, imposteremo il punto finale di essere solo alla sinistra del punto medio corrente. Così cambieremo il punto finale a 7. Vedete quello che è appena è successo qui, però? Guardate qui ora. 

Start è ora maggiore di fine. In effetti, le due estremità della nostra gamma hanno attraversato, e il punto di partenza è ora, dopo il punto finale. Beh, questo non lo fa alcun senso, giusto? Così ora, quello che possiamo dire è che abbiamo avere una matrice sub di dimensioni 0. E una volta che siamo arrivati ​​al questo punto, possiamo ora garantire che elemento 16 non esiste nella matrice, perché il punto di partenza e punto finale hanno attraversato. E quindi non è lì. Ora, si noti che questo è un po ' diverso rispetto al punto di inizio e fine punto è la stessa. Se fossimo stati alla ricerca per 17, sarebbe stato nella matrice, e il punto iniziale e il punto finale di quella dell'ultima iterazione prima di quei punti attraversati, avremmo trovato 17 lì. E 'solo quando attraversano che possiamo garantire che l'elemento non fa esistere nella matrice. 

Quindi cerchiamo di prendere un sacco meno passaggi di ricerca lineare. Nel peggiore dei casi, abbiamo avuto per dividere una lista di n elementi ripetutamente a metà per trovare il bersaglio, sia perché l'elemento di destinazione sarà da qualche parte negli ultimi divisione, o non esiste affatto. Quindi, nel caso peggiore, dobbiamo dividere i array-- fai a saperlo? Log di n volte; noi tagliare il problema in mezzo un certo numero di volte. Quel numero di volte che è log n. 

Qual è la migliore delle ipotesi? Beh, la prima volta che ci siamo calcolare il punto medio, troviamo quello che stiamo cercando. In tutti i precedenti esempi su ricerca binaria abbiamo appena andato oltre, se avessimo state cercando l'elemento 15, avremmo trovato subito. E 'stato proprio all'inizio. Questo è stato il punto medio di il primo tentativo di una scissione di una divisione in ricerca binaria. 

E così nel peggiore caso, ricerca binaria corre in log n, che è sostanzialmente migliore di ricerca lineare, nel caso peggiore. Nel migliore dei casi, binario ricerca viene eseguito in omega di 1. Così la ricerca binaria è molto meglio di ricerca lineare, ma bisogna fare i conti con il processo di ordinamento la matrice prima di poter sfruttare la potenza di ricerca binaria. 

Sono Doug Lloyd. Questo è CS 50.