[Mūzikas atskaņošanai] 

Doug LLOYD: Nu labi. Tātad binārā meklēšana ir algoritmu mēs varam izmantot atrast elementu iekšpusē masīva. Atšķirībā no lineārās meklēšanu, tas prasa īpašs nosacījums jāizpilda iepriekš, bet tas ir tik daudz efektīvāka, ja šis nosacījums ir, faktiski, met. 

Tātad, kāda ir ideja šeit? tas ir skaldi un valdi. Mēs vēlamies, lai samazinātu izmēru meklēšanas platība uz pusi katru reizi , lai atrastu mērķa numuru. Tas ir, ja šis nosacījums sāk spēlēt, though. Mēs varam tikai palielinātu jaudu novēršot puse no elementiem pat apskatot viņiem ja masīvs ir sakārtots. 

Ja tas ir pilnīgs mix up, mēs varam ne tikai no rokām atbrīvoties puse no elementiem, jo mēs nezinām, ko mēs izmetot. Bet, ja masīvs ir sakārtots, mēs varam darīt, jo mēs zinu, ka viss uz pa kreisi no tā, kur mēs šobrīd esam nedrīkst būt zemāka par vērtība šobrīd mēs esam. Un viss uz tiesības, ja mēs esam ir lielāka nekā vērtība mēs pašlaik meklē. 

Tātad, kāda ir pseudocode soļi bināro meklēšanu? Mēs atkārtot šo procesu, līdz masīvs vai, kā mēs turpinātu cauri, sub bloki, mazāki gabali oriģināls masīvs, ir lielums 0. Aprēķināt viduspunktu Pašreizējās sub masīvs. 

Ja vērtība jūs meklējat ir šajā masīva elementa, apstāties. Jums atrast to. Tas ir lieliski. Pretējā gadījumā, ja mērķis ir mazāk nekā to, kas ir pa vidu, Tātad, ja vērtības mēs meklējam lai ir zemāks nekā tas, ko mēs redzam, vēlreiz atkārtot šo procesu, bet mainīt beigu punktu, tā vietā būt oriģināls pabeigtu pilnu klāstu, , ir tikai pa kreisi par to, kur mēs vienkārši skatījās. 

Mēs zinājām, ka vidējā bija pārāk augsts, vai mērķis bija mazāks nekā vidū, Un tā tas ir jāpastāv, ja to pastāv visos masīva, kaut kur pa kreisi viduspunktā. Un tāpēc mēs noteikti masīvs vieta tikai pa kreisi par viduspunktu kā jaunais beigu punktu. Savukārt, ja mērķis ir lielāks par to, kas ir pa vidu, mēs tieši tā pati process, bet tā vietā mēs mainīt sākumpunktu būt tikai uz labi no viduspunktā mēs vienkārši aprēķināt. Un tad mēs atkal sāktu procesu. 

Pieņemsim vizualizēt to, OK? Tātad tur ir daudz kas notiek, un šeit, bet šeit ir masīvs no 15 elementiem. Un mēs ejam, lai būtu sekotu no daudz vairāk sīkumi šoreiz. Tātad lineārā meklēšanā, mēs bijām tikai rūpējas par mērķi. Bet šoreiz mēs gribam rūp, kur mēs esam sāk izskatīties, kur mēs meklējam apstāšanās, un kas ir viduspunktā Pašreizējās masīva. Tātad, šeit mēs iet ar bināro meklēšanu. Mēs esam diezgan daudz labi iet, vai ne? Es esmu tikai gatavojas nolikt Turpmāk šeit kopa indeksu. Tas ir būtībā tikai tas, ko elements masīva mēs runājam. Ar lineāro meklēšanu, mēs aprūpi, jo mēs ir jāzina, cik daudz elementi mēs atkārtojot vairāk, bet mēs faktiski nav vienalga, ko elements mēs pašlaik meklē. Binārā meklējumos, mēs darām. Un tā tie ir tikai tur kā mazs ceļvedis. 

Tātad, mēs varam sākt, ne? Nu, ne gluži. Atceries, ko es teicu par bināro meklēšanu? Mēs nevaram to darīt, pamatojoties uz nešķiroti masīvs vai kas cits, mēs neesam garantē, ka daži elementi vai vērtības nav nejaušas izmet, kad mēs tikko nolemt ignorēt pusi no masīva. 

Tātad viens solis ar bināro meklēšanu ir jums ir jābūt sakārtoti masīvs. Un jūs varat izmantot jebkuru no šķirošanas algoritmi, mēs esam runājuši par lai saņemtu jums šai pozīcijai. Tāpēc tagad, mēs esam tādā stāvoklī, kur mēs varam veikt bināro meklēšanu. 

Tātad, pieņemsim atkārtojiet procesu soli pa solim un saglabāt dziesmu par to, kas notiek, kā mums iet. Tātad vispirms mums ir jādara, ir aprēķināt viduspunktā pašreizējā masīva. Nu, mēs sakām, mēs esam, pirmkārt visi, kas meklē vērtību 19. Mēs cenšamies, lai atrastu numuru 19. Ar šo pirmo elements masīvs atrodas pie indeksa nulles, un pēdējais elements šis masīvs atrodas indeksā 14. Un tāpēc mēs aicinām šos sākumu un beigas. 

Tātad mēs aprēķināt viduspunktā ar pievienojot 0 plus 14 dalīts ar 2; diezgan vienkārši viduspunktā. Un mēs varam teikt, ka Tagad viduspunktā ir 7. Tātad ir 15, ko mēs meklējam? Nē tā nav. Mēs meklējam 19. Bet mēs zinām, ka 19 ir lielāks nekā tas, ko mēs atradām vidū. 

Tātad, ko mēs varam darīt, ir mainīt sākumpunktu būt tikai pa labi no viduspunktā, un atkal atkārtojiet procesu. Un, kad mēs to darām, mēs tagad teikt Jauns posms punkts ir masīvs vieta 8. Ko mēs esam darījuši efektīvi ir ignorēja viss pa kreisi 15. Mēs esam likvidēta pusi problēmas, un tagad, tā vietā, lai meklētu vairāk nekā 15 elementi mūsu masīva, mums ir tikai meklēt vairāk nekā 7. Tātad 8 ir jauna sākuma punkts. 14. joprojām ir beigu punktu. 

Un tagad, mēs iet pār to vēlreiz. Mēs aprēķināt jauno viduspunktā. 8 plus 14 ir 22, dalīts ar 2 ir 11. Vai tas, ko mēs meklējam? Nē tā nav. Mēs meklējam vērtību, kas ir mazāk nekā tas, ko mēs tikko atrasts. Tātad mēs ejam atkārtot procesu no jauna. Mēs ejam, lai mainītu beigu punkts būt tikai pa kreisi no viduspunktā. Tātad jaunais beigu punkts kļūst par 10. Un tagad, tas ir tikai daļa no masīvs mums kārtot cauri. Tāpēc mēs esam tagad novērsti 12 no 15 elementiem. Mēs zinām, ka, ja 19 pastāv masīva, to ir jāpastāv kaut kur starp elementa skaits 8 un elementu skaits 10. 

Tātad mēs aprēķināt jauno viduspunktu vēlreiz. 8 plus 10 ir 18, dalīts ar 2 ir 9. Un, šajā gadījumā, izskatās, tad mērķis ir pa vidu. Mēs atradām tieši to, ko mēs meklējam. Mēs varam apturēt. Mēs veiksmīgi pabeigta bināro meklēšanu. Viss kārtībā. Tātad mēs zinām šo algoritmu darbojas, ja mērķis ir kaut kur iekšpusē masīva. Vai šo algoritmu darbu, ja mērķis ir ne masīvu? Nu, sāksim to atkal, un šis laiks, pieņemsim meklēt elementa 16, kas vizuāli mēs varam redzēt neeksistē nekur masīvā. 

Starta punkts ir atkal 0. Beigu punkts ir atkal 14. Tie ir rādītāji par pirmo un pēdējie elementi pilnīgu masīva. Un mēs iet caur procesu mēs vienkārši pārdzīvoja atkal mēģina atrast 16, kaut gan vizuāli, mēs varam jau pateikt, ka tas nav būs tur. Mēs vienkārši vēlamies, lai pārliecinātos, ka šo algoritmu būs, patiesībā, joprojām strādā kaut kādā veidā un ne tikai atstāt mums iestrēdzis bezgalīgu cilpu. 

Tātad, kas ir solis pirmais? Aprēķināt viduspunktu Pašreizējās masīva. Kas ir viduspunktā Pašreizējās masīva? Nu, tas ir 7, vai ne? 14 plus 0 dalīts ar 2 ir 7. Ir 15, ko mēs meklējam? Nē. Tas ir diezgan tuvu, bet mēs meklējam par kuru vērtība nedaudz lielāks nekā. 

Tātad mēs zinām, ka tas notiek, lai nekur pa kreisi 15. Mērķis ir lielāks nekā to, kas ir viduspunktā. Un tāpēc mēs noteikti jaunu sākumpunktu uz būt tikai pa labi no vidus. Viduspunktā pašlaik 7, tāpēc teiksim jaunais sākuma punkts ir 8. Un tas, ko mēs esam efektīvi darīts atkal tiek ignorēts visa kreisā puse no masīva. 

Tagad mēs atkārtojiet apstrādāt vēl vienu reizi. Aprēķināt jauno viduspunktā. 8 plus 14 ir 22, dalīts ar 2 ir 11. Ir 23, ko mēs meklējam? Diemžēl, nē. Mēs meklējam vērtību kas ir mazāk nekā 23. Un tā šajā gadījumā, mēs ejam lai mainītu beigu punktu, ir tikai pa kreisi no pašreizējās viduspunktā. Pašreizējā viduspunktā ir 11, un tāpēc mēs uzstādītu jaunu beigu punktu par nākamo reizi, kad ejam cauri šim procesam līdz 10. 

Atkal, mēs iet caur procesu vēlreiz. Aprēķināt viduspunktā. 8 plus 10 dalīts ar 2 ir 9. Ir 19, ko mēs meklējam? Diemžēl, nē. Mēs joprojām meklējam vairāki mazāks par to. Tātad mēs mainīt galapunkts šoreiz , ir tikai pa kreisi no viduspunktā. Viduspunktā pašlaik 9, lai gala punkts būs 8. Un tagad mēs esam tikai meklējam vienā elementu masīvs. 

Kas ir viduspunktā šī masīva? Nu, tas sākas 8, tas beidzas 8, viduspunktā ir 8. Vai tas, ko mēs meklējam? Vai mēs meklējam 17? Nē, mēs meklējam 16. Tātad, ja tas eksistē masīva, tas ir jāpastāv kaut kur pa kreisi, kur mēs pašlaik esam. Tātad, ko mēs gatavojamies darīt? Nu, mēs iestatītu beigu punktu, ir tikai pa kreisi no pašreizējās viduspunktā. Tātad mēs mainīt beigu punktu 7. Vai jūs redzat, ko tikko notika šeit, lai gan? Paskaties šeit tagad. 

Sākt tagad ir lielāka nekā gala. Faktiski abi gali Mūsu masīvs ir šķērsojuši, un sākuma punkts ir tagad pēc beigu punktu. Nu, tas nav kāda jēga, vai ne? Tāpēc tagad, ko mēs varam teikt, ir, mēs ir sub masīvs izmēra 0. Un, kad mēs esam iepazinuši Šajā brīdī mēs varam tagad garantēt, ka elements 16 neeksistē masīvā, jo sākumpunktu un beigu punkts ir šķērsojuši. Un tāpēc tas nav tur. Tagad, ievērosiet, ka tas ir nedaudz atšķirīgs nekā sākuma punktu un beigu punktu ir vienādi. Ja mēs būtu bijuši meklējam par 17, tas būtu bijusi masīva, un starta punktu un beigu punkts šo pēdējo atkārtojuma Pirms šie punkti šķērsoja, mēs būtu atraduši 17 tur. Tas ir tikai tad, kad viņi šķērso, ka mēs varam garantēt, ka elements nav pastāv masīva. 

Tātad pieņemsim daudz mazāk soļi nekā lineāri meklēšanā. Sliktākajā gadījumā, mums bija sadalīt sarakstu n elementiem atkārtoti pusē, lai atrastu mērķa, nu tāpēc, ka mērķa elements būs kaut kur pēdējais nodaļa, vai arī tas neeksistē vispār. Tātad sliktākajā gadījumā, mums ir sadalīt array-- jūs zināt? Log n reizes; mēs ir samazināt šo problēmu pusi noteiktu skaitu reižu. Tas, cik reižu ir log n. 

Kāds ir labākais scenārijs? Nu, pirmā reize, kad mēs aprēķināt viduspunktā, mēs redzam to, ko mēs meklējam. Visos iepriekšējos piemēri par bināro meklēšanu mēs esam tikko aizgājuši vairāk, ja mēs būtu meklējis elementa 15, mēs esam secinājuši, ka nekavējoties. Tas bija pašā sākumā. Tas bija viduspunktā pirmais mēģinājums split par sadalīšanu, kas bināro meklēšanu. 

Un tā sliktākā gadījumā, bināro meklēšanu darbojas log n, kas ir ievērojami labāk kā lineāru meklēšanu, sliktākajā gadījumā. Labākajā gadījumā, bināro meklēšana trašu omega 1. Tātad binārā meklēšana ir daudz labāk nekā lineārā meklēšanu, bet jums ir tikt galā ar procesu šķirošanas savu masīvs pirmais, pirms jūs varat sviras varu bināro meklēšanu. 

Es esmu Doug Lloyd. Tas ir CS 50.