>> [Muzika]
>> DOUG Lloyd: NĂ« rregull.
Pra, kĂ«rko binar Ă«shtĂ« njĂ« Algorithm ne mund tĂ« pĂ«rdorim
pĂ«r tĂ« gjetur njĂ« element brenda njĂ« grup.
Ndryshe kĂ«rkim lineare, ajo kĂ«rkon njĂ« kusht tĂ« veĂ§antĂ« tĂ« plotĂ«sohen paraprakisht,
por ajo Ă«shtĂ« aq shumĂ« mĂ« efikas nĂ«se se gjendja Ă«shtĂ«, nĂ« fakt, u takuan.
>> Pra, Ă§farĂ« Ă«shtĂ« ideja kĂ«tu?
Ă«shtĂ« pĂ«rĂ§a dhe sundo.
Ne duam tĂ« zvogĂ«luar madhĂ«sinĂ« e zona e kĂ«rkimit nga gjysmĂ« Ă§do herĂ«
nĂ« mĂ«nyrĂ« qĂ« tĂ« gjeni njĂ« numĂ«r tĂ« synuar.
Kjo Ă«shtĂ« ajo ku se gjendja vjen nĂ« lojĂ«, edhe pse.
Ne vetĂ«m mund tĂ« levave fuqinĂ« e eliminimin gjysma e elementeve
edhe pa e kĂ«rkuar nĂ« ata nĂ«se array Ă«shtĂ« e renditura.
>> NĂ« qoftĂ« se kjo Ă«shtĂ« njĂ« pĂ«rzierje e plotĂ« lart, ne nuk mund vetĂ«m nga dora
hidhni gjysmĂ«n e elementeve, sepse ne nuk e dimĂ« se Ă§farĂ« ne jemi hidhni.
Por nĂ« qoftĂ« se array Ă«shtĂ« e renditura, ne mund ta bĂ«jmĂ« kĂ«tĂ«, sepse ne
e di se Ă§do gjĂ« nĂ« la e ku ne aktualisht jemi tĂ«
duhet tĂ« jetĂ« mĂ« e ulĂ«t se Vlera ne jemi aktualisht nĂ«.
Dhe Ă§do gjĂ« tĂ« e drejta e ku jemi
duhet tĂ« jetĂ« mĂ« i madh se vlera ne jemi aktualisht nĂ« kĂ«rkim nĂ«.
>> Pra, Ă§farĂ« Ă«shtĂ« pseudokod hapat pĂ«r kĂ«rkimin binar?
Ne pĂ«rsĂ«ris kĂ«tĂ« proces deri nĂ« grup ose, si ne tĂ« vazhdojĂ« pĂ«rmes,
nĂ«n vargjeve, copa tĂ« vogla tĂ« array origjinal, Ă«shtĂ« i madhĂ«sisĂ« 0.
Llogarit midpoint e array aktuale sub.
>> NĂ«se vlera jeni duke kĂ«rkuar pĂ«r tĂ« Ă«shtĂ« nĂ« kĂ«tĂ« element tĂ« vektorit, tĂ« ndaluar.
Keni gjetur atĂ«.
Kjo Ă«shtĂ« e madhe.
PĂ«rndryshe, nĂ« qoftĂ« se objektivi Ă«shtĂ« mĂ« pak se Ă§farĂ« Ă«shtĂ« nĂ« mes,
kĂ«shtu qĂ« nĂ«se vlera ne jemi duke kĂ«rkuar pĂ«r tĂ« Ă«shtĂ« mĂ« e ulĂ«t se ajo qĂ« ne shohim,
pĂ«rsĂ«ris kĂ«tĂ« proces pĂ«rsĂ«ri, por ndryshojĂ« pikĂ«n fund, nĂ« vend
pĂ«r tĂ« qenĂ« origjinale pĂ«rfunduar koleksion tĂ« plotĂ«,
tĂ« jetĂ« vetĂ«m nĂ« tĂ« majtĂ« e ku ne vetĂ«m shikuar.
>> Ne e dinim se mesme ishte shumĂ« i lartĂ«, ose objektivi ishte mĂ« pak se mes,
dhe kĂ«shtu ajo duhet tĂ« ekzistojĂ«, nĂ«se ajo ekziston fare nĂ« grup,
diku nĂ« tĂ« majtĂ« tĂ« midpoint.
Dhe kĂ«shtu qĂ« ne do tĂ« vendosur array vend vetĂ«m nĂ« tĂ« majtĂ«
i midpoint si pikĂ« e re nĂ« fund.
NĂ« anĂ«n tjetĂ«r, nĂ« qoftĂ« se objektivi Ă«shtĂ« mĂ« tĂ« madhe se ajo qĂ« Ă«shtĂ« nĂ« mes,
ne bĂ«jmĂ« tĂ« njĂ«jtĂ«n gjĂ« e saktĂ« proces, por nĂ« vend tĂ« kĂ«saj ne
ndryshojĂ« pikĂ«nisjen tĂ« jetĂ« vetĂ«m nĂ« tĂ« djathtĂ« tĂ« midpoint
ne vetĂ«m llogaritur.
Dhe pastaj, ne fillojmĂ« procesin pĂ«rsĂ«ri.
>> Le tĂ« kujtoj kĂ«tĂ«, nĂ« rregull?
Pra, ka njĂ« shumĂ« ndodh dhe nĂ« kĂ«tu, por kĂ«tu Ă«shtĂ« njĂ« grup prej 15 elementeve.
Dhe ne jemi duke shkuar pĂ«r tĂ« mbajtur gjurmĂ«t e njĂ« shumĂ« mĂ« tĂ« gjĂ«ra nĂ« kĂ«tĂ« kohĂ«.
Pra, nĂ« kĂ«rkim linear, ne ishim vetĂ«m kujdeset pĂ«r njĂ« objektiv.
Por kĂ«tĂ« herĂ« ne duam tĂ« kujdes pĂ«r ku jemi ne
filluar tĂ« duken, ku jemi ndalur duke kĂ«rkuar,
dhe Ă§farĂ« Ă«shtĂ« midpoint e array aktuale.
Pra, kĂ«tu ne do tĂ« shkojmĂ« me kĂ«rkimin binar.
Ne jemi shumĂ« e shumĂ« tĂ« mirĂ« pĂ«r tĂ« shkuar, e drejtĂ«?
UnĂ« jam vetĂ«m duke shkuar pĂ«r tĂ« vĂ«nĂ« poshtĂ« poshtĂ« kĂ«tu njĂ« grup i treguesve.
Kjo Ă«shtĂ« nĂ« thelb vetĂ«m ajo qĂ« elementi e grup ne jemi duke folur rreth.
Me kĂ«rkimin lineare, ne kujdes, duke qenĂ« se ne
duhet tĂ« dini se sa Elementet ne jemi iterating mbi,
por ne fakt nuk e kujdesit Ă§farĂ« element ne jemi aktualisht nĂ« kĂ«rkim nĂ«.
NĂ« kĂ«rkim binar, ne bĂ«jmĂ«.
Dhe kĂ«shtu ata janĂ« vetĂ«m atje si njĂ« udhĂ«zues tĂ« vogĂ«l.
>> Pra, ne mund tĂ« fillojnĂ«, apo jo?
E pra, jo fare.
Mos harroni atĂ« qĂ« kam thĂ«nĂ« pĂ«r kĂ«rkimin binar?
Ne nuk mund ta bĂ«jĂ« kĂ«tĂ« nĂ« njĂ« array Unsorted ose tjetĂ«r,
ne nuk jemi tĂ« garantuar se elemente ose vlerat e caktuara nuk janĂ« tĂ«
tĂ« qenit aksidentalisht fshi kur ne vetĂ«m
vendosni tĂ« injorojĂ« gjysmĂ«n e vektorit.
>> Pra, hap njĂ« me kĂ«rkimin binar Ă«shtĂ« qĂ« ju duhet tĂ« keni njĂ« rrjet tĂ« renditura.
Dhe ju mund tĂ« pĂ«rdorni ndonjĂ« nga klasifikim Algoritme ne kemi biseduar pĂ«r
pĂ«r tĂ« merrni ju nĂ« atĂ« pozitĂ«.
Deri tani, ne jemi nĂ« njĂ« pozicion ku ne mund tĂ« kryejĂ« kĂ«rkimin binar.
>> Pra, le tĂ« pĂ«rsĂ«ris procesin hap pas hapi dhe pĂ«r tĂ« mbajtur
gjurmĂ«t e asaj qĂ« po ndodh si tĂ« shkojmĂ«.
Pra, sĂ« pari ne duhet tĂ« bĂ«jmĂ« Ă«shtĂ« tĂ« llogaritur midpoint e array aktuale.
E pra, ne do tĂ« themi ne jemi, sĂ« pari tĂ« gjithĂ«, duke kĂ«rkuar pĂ«r vlerĂ«n 19.
Ne jemi duke u pĂ«rpjekur pĂ«r tĂ« gjetur numrin 19.
Elementi i parĂ« i kĂ«saj grup Ă«shtĂ« vendosur nĂ« indeksin zero,
dhe elementi i fundit i kĂ«saj grup Ă«shtĂ« vendosur nĂ« indeksin e 14.
Dhe kĂ«shtu qĂ« ne do tĂ« thĂ«rrasĂ« ato fillimin dhe fundin.
>> Pra, ne llogarisim midpoint nga duke shtuar plus 14 0 ndarĂ« nga 2;
midpoint shumĂ« i thjeshtĂ«.
Dhe ne mund tĂ« themi se midpoint tani Ă«shtĂ« 7.
Pra Ă«shtĂ« 15 ajo qĂ« ne jemi duke kĂ«rkuar pĂ«r?
Jo nuk eshte.
Ne jemi nĂ« kĂ«rkim 19.
Por ne e dimĂ« se 19 Ă«shtĂ« mĂ« i madh se ajo qĂ« kemi gjetur nĂ« mes.
>> Pra, Ă§farĂ« mund tĂ« bĂ«jmĂ« Ă«shtĂ« ndryshojĂ« pikĂ«nisjen
tĂ« jetĂ« vetĂ«m nĂ« tĂ« djathtĂ« e midpoint, dhe pĂ«rsĂ«risin procesin pĂ«rsĂ«ri.
Dhe kur e bĂ«jmĂ« kĂ«tĂ«, ne tani thonĂ« se pikĂ« e re e fillimit Ă«shtĂ« koleksion vend 8.
Ajo qĂ« ne kemi bĂ«rĂ« nĂ« mĂ«nyrĂ« efektive Ă«shtĂ« gjithĂ§ka injoruar nĂ« tĂ« majtĂ« tĂ« 15.
Ne e kemi eliminuar gjysmĂ«n e problemit, dhe tani,
nĂ« vend qĂ« tĂ« kĂ«rkoni mbi 15 elemente nĂ« grup tonĂ«,
ne vetĂ«m duhet tĂ« kĂ«rkoni mbi 7.
Pra 8 Ă«shtĂ« pikĂ« e re e fillimit.
14 Ă«shtĂ« ende pikĂ« nĂ« fund.
>> Dhe tani, ne do tĂ« shkojmĂ« mbi kĂ«tĂ« pĂ«rsĂ«ri.
Ne llogarisim midpoint e ri.
8 plus 14 Ă«shtĂ« 22, tĂ« ndarĂ« nga 2 Ă«shtĂ« 11.
A Ă«shtĂ« kjo ajo qĂ« ne jemi duke kĂ«rkuar pĂ«r?
Jo nuk eshte.
Ne jemi duke kĂ«rkuar pĂ«r njĂ« vlerĂ« qĂ« Ă«shtĂ« mĂ« pak se ajo qĂ« ne vetĂ«m e gjeti.
Pra, ne jemi duke shkuar pĂ«r tĂ« pĂ«rsĂ«ritur procesi pĂ«rsĂ«ri.
Ne jemi duke shkuar pĂ«r tĂ« ndryshuar pikĂ«n nĂ« fund tĂ« tĂ« jetĂ« vetĂ«m nĂ« tĂ« majtĂ« tĂ« midpoint.
Pra, pikĂ« e re nĂ« fund tĂ« bĂ«het 10.
Dhe tani, kjo Ă«shtĂ« vetĂ«m njĂ« pjesĂ« e array ne kemi pĂ«r tĂ« zgjidhur nĂ«pĂ«rmjet.
Pra, ne kemi eliminuar tani 12 e 15 elementeve.
Ne e dimĂ« se nĂ«se 19 ekziston nĂ« grup, atĂ«
duhet tĂ« ekzistojĂ« diku nĂ« mes tĂ« elementit numĂ«r 8 dhe element numĂ«r 10.
>> Pra, ne llogarisim midpoint e re pĂ«rsĂ«ri.
8 plus 10 Ă«shtĂ« 18, tĂ« ndarĂ« nga 2 Ă«shtĂ« 9.
Dhe nĂ« kĂ«tĂ« rast, ja, Objektivi Ă«shtĂ« nĂ« mes.
Ne kemi gjetur pikĂ«risht ajo qĂ« ne jemi duke kĂ«rkuar pĂ«r tĂ«.
Ne mund tĂ« ndalet.
Ne pĂ«rfundoi me sukses njĂ« kĂ«rkim binar.
NĂ« rregull.
Pra, ne e dimĂ« kĂ«tĂ« algoritmi punon nĂ« qoftĂ« se objektivi Ă«shtĂ«
diku brenda array.
E bĂ«n kĂ«tĂ« punĂ« algorithm nĂ«se objektiv nuk Ă«shtĂ« grup?
E pra, le tĂ« fillojĂ« atĂ« pĂ«rsĂ«ri, dhe kĂ«tĂ« herĂ«,
le tĂ« shohim pĂ«r elementin 16, e cila vizualisht ne mund tĂ« shohim
nuk ekziston askund nĂ« rrjet.
>> Pika e fillimit Ă«shtĂ« pĂ«rsĂ«ri 0.
Pika Fundi Ă«shtĂ« pĂ«rsĂ«ri 14.
Ata janĂ« indekset e parĂ« dhe Elementet e fundit tĂ« vektorit tĂ« plotĂ«.
Dhe ne do tĂ« kalojnĂ« nĂ«pĂ«r procesin e ne vetĂ«m shkoi nĂ«pĂ«r pĂ«rsĂ«ri, duke u pĂ«rpjekur pĂ«r tĂ« gjetur 16,
edhe pse me sy, ne tashmĂ« mund tĂ« them se kjo nuk do tĂ« jetĂ« atje.
Ne vetĂ«m duam tĂ« sigurohemi kĂ«tĂ« algorithm do tĂ«, nĂ« fakt, ende punojnĂ« nĂ« njĂ« farĂ« mĂ«nyre
dhe jo vetĂ«m tĂ« na lĂ«nĂ« mbĂ«rthyer nĂ« njĂ« lak tĂ« pafund.
>> Pra, Ă§farĂ« Ă«shtĂ« hapi i parĂ«?
Llogarit midpoint e array aktuale.
Ă‡farĂ« Ă«shtĂ« midpoint e array aktuale?
E pra, kjo Ă«shtĂ« 7, e drejtĂ«?
14 plus 0 ndarĂ« nga 2 Ă«shtĂ« 7.
Ă‹shtĂ« 15 atĂ« qĂ« ne jemi duke kĂ«rkuar pĂ«r?
Jo.
Ă‹shtĂ« mjaft i afĂ«rt, por ne jemi duke kĂ«rkuar pĂ«r njĂ« vlerĂ« pak mĂ« tĂ« madhe se kaq.
>> Pra, ne e dimĂ« se ajo do tĂ« tĂ« jetĂ« askund nĂ« tĂ« majtĂ« tĂ« 15.
Objektiv Ă«shtĂ« mĂ« e madhe se Ă§farĂ« Ă«shtĂ« nĂ« midpoint.
Dhe kĂ«shtu qĂ« ne kemi vendosur pikĂ« tĂ« re tĂ« fillojĂ« tĂ« tĂ« jetĂ« vetĂ«m pĂ«r tĂ« drejtĂ«n e mes.
Midpoint Ă«shtĂ« aktualisht 7, kĂ«shtu qĂ« le tĂ« themi pika e re e fillimit Ă«shtĂ« 8.
Dhe ajo qĂ« ne kemi nĂ« mĂ«nyrĂ« efektive bĂ«rĂ« pĂ«rsĂ«ri Ă«shtĂ« injoruar
tĂ« gjithĂ« gjysmĂ«n e majtĂ« tĂ« vektorit.
>> Tani, ne pĂ«rsĂ«ris procesin e njĂ« mĂ« shumĂ« kohĂ«.
Llogaritni midpoint e ri.
8 plus 14 Ă«shtĂ« 22, tĂ« ndarĂ« nga 2 Ă«shtĂ« 11.
Ă‹shtĂ« 23 atĂ« qĂ« ne jemi duke kĂ«rkuar pĂ«r?
PĂ«r fat tĂ« keq, nuk ka.
Ne jemi duke kĂ«rkuar pĂ«r njĂ« vlerĂ« tĂ« qĂ« Ă«shtĂ« mĂ« pak se 23.
Dhe kĂ«shtu nĂ« kĂ«tĂ« rast, ne jemi duke shkuar pĂ«r tĂ« ndryshuar pikĂ«n fund tĂ« jetĂ« vetĂ«m
nĂ« tĂ« majtĂ« tĂ« midpoint e tanishĂ«m.
Midpoint aktual Ă«shtĂ« 11, dhe kĂ«shtu qĂ« ne do tĂ« vendosur nĂ« pikĂ«n e re nĂ« fund
pĂ«r herĂ«n tjetĂ«r ne do tĂ« shkojmĂ« pĂ«rmes kĂ«tij procesi deri nĂ« 10.
>> PĂ«rsĂ«ri, ne do tĂ« shkojmĂ« nĂ«pĂ«r procesin pĂ«rsĂ«ri.
Llogarit midpoint.
8 plus 10 ndarĂ« nga 2 Ă«shtĂ« 9.
Ă‹shtĂ« 19 atĂ« qĂ« ne jemi duke kĂ«rkuar pĂ«r?
PĂ«r fat tĂ« keq, nuk ka.
Ne jemi ende nĂ« kĂ«rkim tĂ« njĂ« numĂ«r mĂ« pak se.
Pra, ne do tĂ« ndryshojĂ« pikĂ«n e fundit kĂ«tĂ« herĂ« tĂ« jetĂ« vetĂ«m nĂ« tĂ« majtĂ« tĂ« midpoint.
Midpoint Ă«shtĂ« aktualisht 9, kĂ«shtu qĂ« pikĂ« nĂ« fund do tĂ« jetĂ« 8.
Dhe tani, ne jemi vetĂ«m nĂ« kĂ«rkim nĂ« njĂ« grup tĂ« vetĂ«m element.
>> Ă‡farĂ« Ă«shtĂ« midpoint e kĂ«saj grup?
E pra, ajo fillon nĂ« 8, ajo pĂ«rfundon nĂ« 8, midpoint Ă«shtĂ« 8.
A Ă«shtĂ« kjo ajo qĂ« ne jemi duke kĂ«rkuar pĂ«r?
A jemi duke kĂ«rkuar pĂ«r 17?
Jo, ne jemi duke kĂ«rkuar pĂ«r 16.
Pra, nĂ«se ajo ekziston nĂ« grup, ajo duhet tĂ« ekzistojĂ« diku
nĂ« tĂ« majtĂ« tĂ« ku ne aktualisht janĂ«.
Pra, Ă§farĂ« do tĂ« shkojmĂ« tĂ« bĂ«jmĂ«?
E pra, ne do tĂ« vĂ«nĂ« pikĂ«n nĂ« fund tĂ« jetĂ« vetĂ«m nĂ« tĂ« majtĂ« tĂ« midpoint e tanishĂ«m.
Pra, ne do tĂ« ndryshojĂ« pikĂ«n fund nĂ« 7.
A e shihni se Ă§farĂ« sapo ka ndodhur kĂ«tu, edhe pse?
Look up kĂ«tu tani.
>> Filloni tani Ă«shtĂ« mĂ« i madh sesa nĂ« fund.
Efektive, tĂ« dy skajet e array tonĂ« kanĂ« kaluar,
dhe pika e fillimit Ă«shtĂ« tani pas pikĂ« nĂ« fund.
E pra, kjo nuk ka tĂ« bĂ«jĂ« ndonjĂ« kuptim, apo jo?
Deri tani, ajo qĂ« mund tĂ« them Ă«shtĂ« qĂ« ne kanĂ« njĂ« grup nĂ«n tĂ« madhĂ«sisĂ« 0.
Dhe njĂ« herĂ« ne jemi duke marrĂ« pĂ«r kjo pikĂ«, ne tani mund tĂ«
tĂ« garantojĂ« se elementi 16 nuk ekziston nĂ« grup,
sepse pika e fillimit dhe pikĂ« nĂ« fund kanĂ« kaluar.
Dhe kĂ«shtu qĂ« nuk Ă«shtĂ« aty.
Tani, vini re se kjo Ă«shtĂ« pak ndryshme se pika e fillimit dhe nĂ« fund
mĂ« tepĂ«r Ă«shtĂ« e njĂ«jtĂ«.
NĂ«se do tĂ« kishte qenĂ« nĂ« kĂ«rkim pĂ«r 17, ai do tĂ« ketĂ«
qenĂ« nĂ« grup, dhe pika e fillimit dhe pikĂ« nĂ« fund tĂ« atij pĂ«rsĂ«ritje fundit
para se ato pika kaluar, ne do tĂ« kemi gjetur 17 atje.
Ă‹shtĂ« vetĂ«m kur ata kalojnĂ« qĂ« ne mund tĂ« garantojĂ« se elementi nuk ka
ekzistojnĂ« nĂ« rrjet.
>> Pra, le tĂ« marrin njĂ« shumĂ« mĂ« pak Hapat sesa kĂ«rkim linear.
NĂ« rastin mĂ« tĂ« keq, kemi pasur pĂ«r tĂ« ndarĂ« njĂ« listĂ« tĂ« elementeve n
nĂ« mĂ«nyrĂ« tĂ« pĂ«rsĂ«ritur nĂ« gjysmĂ« pĂ«r tĂ« gjetur objektivin, ose pĂ«r shkak se elementi objektiv
do tĂ« jetĂ« diku nĂ« tĂ« fundit ndarje, apo nuk ekziston fare.
Pra, nĂ« rastin mĂ« tĂ« keq, ne duhet tĂ« ndarĂ« tĂ« array-- nuk e dini?
Log i herĂ« n; ne keni pĂ«r tĂ« prerĂ« problemin
nĂ« gjysmĂ«n e njĂ« numĂ«r tĂ« caktuar tĂ« kohĂ«s.
Ky numĂ«r i herĂ« Ă«shtĂ« log n.
>> Ă‡farĂ« Ă«shtĂ« skenari mĂ« i mirĂ«?
E pra, koha qĂ« ne e parĂ« llogaritur midpoint,
ne gjejmĂ« atĂ« qĂ« ne jemi duke kĂ«rkuar pĂ«r.
NĂ« tĂ« gjitha e mĂ«parshme Shembujt nĂ« kĂ«rkim binar
ne kemi shkuar pak mĂ« shumĂ«, nĂ«se do tĂ« kishim qenĂ« nĂ« kĂ«rkim pĂ«r elementin 15,
ne do tĂ« kemi gjetur se menjĂ«herĂ«.
Kjo ishte nĂ« fillim.
Kjo ishte midpoint e pĂ«rpjekja e parĂ« nĂ« njĂ« ndarje
e njĂ« ndarje nĂ« kĂ«rkim binar.
>> Dhe kĂ«shtu nĂ« mĂ« tĂ« keq rast, kĂ«rko binar shkon
nĂ« log n, e cila Ă«shtĂ« nĂ« thelb e mirĂ« se kĂ«rko lineare, nĂ« rastin mĂ« tĂ« keq.
NĂ« rastin mĂ« tĂ« mirĂ«, binar KĂ«rko shkon nĂ« omega e 1.
Pra, kĂ«rko binar Ă«shtĂ« njĂ« shumĂ« mĂ« mirĂ« se kĂ«rkimi lineare,
por ju duhet tĂ« merren me procesin e sorting grup tuaj tĂ« parĂ« para se ju mund tĂ«
levave fuqinĂ« e kĂ«rkimit binar.
>> UnĂ« jam Doug Lloyd.
Kjo Ă«shtĂ« CS 50.