>> ROB BOWDEN: Ciao, sono Rob.
Come ci avvaliamo di una ricerca binaria?
Andiamo a scoprirlo.
Quindi, si noti che questa ricerca stiamo andando di attuare in modo ricorsivo.
Si potrebbe anche implementare la ricerca binaria iterativo, quindi se avete fatto questo,
che è perfettamente bene.
>> Ora in primo luogo, ricordiamo quello che il parametri di ricerca sono destinati ad essere.
Qui, vediamo il valore int, che è dovrebbe essere il valore che l'utente è
cercando.
Vediamo la matrice valori int, che è la matrice in cui siamo
ricerca di valore.
E vediamo int n, che è la lunghezza del nostro array.
>> Ora, la prima cosa in primo luogo.
Noi controlliamo per vedere se n è uguale a 0, in qual caso torniamo false.
Questo è solo dicendo che se abbiamo un vuoto matrice, il valore non è chiaramente in un
matrice vuota, in modo da poter restituire false.
>> Ora, vogliamo davvero fare il binario la ricerca parte di ricerca binaria.
Quindi, vogliamo trovare al centro elemento di questa matrice.
Ecco, diciamo mezzo è uguale a n divisa da 2, poiché l'elemento centrale è
andando essere la lunghezza di la nostra gamma diviso per 2.
Ora stiamo andando a controllare per vedere se l' Elemento centrale è uguale al valore siamo
cercando.
Quindi, se i valori medio uguale valore, abbiamo può restituire true quando abbiamo trovato il
valore nella nostra matrice.
>> Ma se questo non era vero, ora abbiamo bisogno di fare il ricorsiva
fase di ricerca binaria.
Dobbiamo cercare sia per l' sinistra della matrice o al
centro della matrice.
Ecco, diciamo che se i valori al centro è meno di valore, ciò significa che il valore
è superiore al mezzo della matrice.
Così valore deve essere alla destra del elemento che abbiamo appena esaminato.
>> Così qui, stiamo andando a cercare ricorsivamente.
E vedremo che cosa stiamo passando a questo in un secondo.
Ma stiamo andando a cercare l' destra dell'elemento centrale.
E nell'altro caso, ciò significa che valore era inferiore alla metà del
array, e quindi stiamo andando per cercare a fianco.
Ora, la sinistra sta per essere un po 'più facile da guardare.
Quindi, vediamo qui che siamo ricorsivamente chiamando ricerca in cui la prima
argomento è, ancora una volta, il valore stiamo guardando oltre.
Il secondo argomento sarà l' array che stavamo cercando sopra.
E l'ultimo elemento è ora centrale.
Ricordate l'ultimo parametro è il nostro int n, in modo che la lunghezza del nostro array.
>> Nella chiamata ricorsiva per la ricerca, siamo ora dicendo che la lunghezza del
array è centrale.
Quindi, se la nostra gamma era di dimensioni 20 e cercato all'indice 10, in quanto mezzo è
20 diviso 2, questo significa che siamo passando 10 come nuovo
lunghezza del nostro array.
Ricordate che quando si ha una matrice di lunghezza 10, significa che il valido
elementi sono negli indici da 0 a 9.
Quindi questo è esattamente ciò che vogliamo specificare la nostra gamma aggiornata - sinistra
matrice dall'elemento centrale.
>> Così, guardando a destra è un po 'più difficile.
Ora in primo luogo, consideriamo la lunghezza della matrice a destra della
elemento centrale.
Quindi, se la nostra matrice era di dimensione n, allora la nuovo array sarà di dimensione n meno
meno centrale 1.
Quindi, pensiamo di n meno di mezzo.
>> Anche in questo caso, se la matrice fosse di dimensioni 20 e dividiamo per 2 per ottenere la metà,
così il mezzo è 10, allora n meno mezzo sta per darci 10, quindi 10
elementi a destra del centro.
Ma abbiamo anche questo meno 1, dal momento che non vogliamo
includere mezzo stesso.
Così n meno di mezzo meno 1 ci dà l' numero totale di elementi a destra
dell'indice medio nella matrice.
>> Ora qui, ricordare che la centrale parametro è l'array valori.
Così qui, stiamo passando un I valori aggiornati array.
Questi valori plus plus mezzo 1 è in realtà dire ricorsivamente chiama
ricerca, passando in un nuovo array, dove nuova matrice che inizia a metà
più uno dei nostri valori dell'array originale.
>> Una sintassi alternativa per questo, ora che hai iniziato a vedere i puntatori, è
I valori Ampersand più centrale 1.
Quindi, prendete l'indirizzo del centro più un elemento di valori.
>> Ora, se tu non fossi comodo modifica di un array come quello,
potrebbe anche aver implementato questo utilizzando una funzione di supporto ricorsiva, dove
che la funzione di supporto prende più argomenti.
Così, invece di prendere solo il valore, matrice, e la dimensione della matrice,
la funzione di supporto potrebbe richiedere più argomenti, tra cui l'indice inferiore
che si preoccupano della matrice e l'indice superiore che si cura
sulla matrice.
>> E quindi mantenere traccia dei valori inferiori indice e l'indice superiore, non lo fanno
necessario modificare mai l' valori originali array.
Si può solo continuare a utilizzare la matrice valori.
Ma qui, notiamo non abbiamo bisogno di un aiuto funzionare finché siamo
disposti a modificare l'originale valori array.
Siamo disposti a passare in un valori aggiornati.
>> Ora, non possiamo ricerca binaria su una matrice che è indifferenziati.
Quindi, cerchiamo di ottenere questo risolto.
Ora, si noti che tipo è passato due parametri int valori, che rappresenta l'
matrice che stiamo ordinamento, e int n, che è la lunghezza della matrice che
stiamo ordinamento.
Così, qui vogliamo implementare un algoritmo di ordinamento
distante o di n squadrato.
Si può scegliere bubble sort, selezione ordinamento, o insertion sort, o
qualche altro tipo che non abbiamo visto in classe.
Ma qui, stiamo andando a utilizzare selection sort.
>> Quindi, stiamo andando a scorrere sull'intera matrice.
Bene, qui vediamo che stiamo scorrendo da 0 a n meno 1.
Perché non tutta la strada fino al n?
Beh, se abbiamo già risolto il primo n meno 1 elementi, poi il
ultimo elemento di ciò che deve essere già nel posto giusto, in modo da classificare over
l'intero array.
>> Ora, ricordare come la selezione ordinamento funziona.
Stiamo per andare oltre l'intero array cercando il valore minimo in
la matrice e il bastone che all'inizio.
Poi abbiamo intenzione di andare oltre l'intero matrice ancora cercando il secondo
più piccolo elemento, e bastone che nella seconda posizione nella
matrice, e così via.
Quindi, questo è ciò che questo sta facendo.
>> Qui, stiamo vedendo che siamo impostando la corrente minima
valore per l'indice i-esimo.
Così la prima iterazione, stiamo andando considerare il valore minimo sia
l'inizio della nostra matrice.
Poi, stiamo andando a scorrere la resto della matrice, controllando
vedere se ci sono elementi più piccolo quello che siamo attualmente
considerando il minimo.
>> Quindi, ecco, i valori j più uno - che è meno di quello che stiamo attualmente
considerando il minimo.
Poi andremo ad aggiornare quello che pensiamo che è il minimo per
indice j più 1.
Quindi, fare che tutta la matrice, e dopo questo ciclo for, minimo
dovrebbe essere l'elemento minimo da la posizione i-esima dell'array.
>> Una volta che abbiamo che, possiamo scambiare il valore minimo nella posizione i-esima
nella matrice.
Quindi questo è solo uno swap standard.
Noi conserviamo in un valore temporaneo - il valore i-esimo dell'array -
mettere in valore i-esimo dell'array l' valore minimo che ci appartiene,
e quindi memorizzare nuovamente dentro cui la valore minimo di corrente era la
i-esimo valore nella matrice, così che non abbiamo perdiamo.
>> Quindi, che prosegue sulla l'iterazione successiva.
Inizieremo cercando il secondo valore minimo e inserire che nella
seconda posizione.
Nella terza iterazione, cercheremo il valore minimo e terzo inserto
che nella terza posizione, e così fino a quando abbiamo un array ordinato.
Il mio nome è Rob, e questo era selection sort.