[Ag seinm ceoil] DOUG LLOYD: Ceart go. Mar sin, tá cuardaigh dénártha ina algartam féidir linn a úsáid chun teacht ar an eilimint taobh istigh de eagar. Murab ionann agus cuardaigh líneach, éilíonn sé coinníoll speisialta a shásamh roimh ré, ach tá sé sin i bhfad níos éifeachtaí má go bhfuil an coinníoll, i ndáiríre, le chéile. Mar sin, cad é an smaoineamh anseo? tá sé scoilt agus conquer. Is mian linn a laghdú ar an méid an limistéar cuardaigh ag leath gach uair d'fhonn a fháil ar roinnt sprioc. Tá sé seo nuair coinníoll sin Tagann i spraoi, cé. Is féidir linn a ghiaráil ach amháin an chumhacht de deireadh a chur leath de na heilimintí gan fiú féachaint ar dóibh má tá an eagar curtha in eagar. Má tá sé ina meascán iomlán suas, ní féidir linn ach amach as an lámh shábháil leath de na heilimintí, mar gheall ar níl a fhios againn cad tá muid ag chaitheamh. Ach má tá an eagar curtha in eagar, Is féidir linn a dhéanamh go, mar gheall orainn fhios go bhfuil gach rud ar an d'fhág an áit ina bhfuil muid faoi láthair Ní mór a bheith níos ísle ná an luach táimid faoi láthair ag. Agus gach rud go dtí an ceart áit a bhfuil muid Ní mór a bheith níos mó ná an luach táimid ag lorg faoi láthair ag. Mar sin, cad é an pseudocode céimeanna ar chuardach dhénártha? Arís againn an bpróiseas seo go dtí an eagar nó, mar a théann muid trí, fo arrays, píosaí beaga de an eagar bunaidh, de mhéid 0. Ríomh an lárphointe de na eagar fo reatha. Má tá an luach bhfuil tú ag lorg sa mhéid is go gné den eagar, stad. Fuair ​​tú é. Go mór. Seachas sin, má tá an sprioc níos lú ná cad atá ag an lár, mar sin má tá an luach beimid ag féachaint ar feadh níos ísle ná an méid a fheiceann muid, arís an próiseas seo arís, ach athrú ar an pointe deiridh, ina ionad sin a bheith ar an bunaidh comhlánaigh sraith iomlán, a bheith díreach ar an taobh clé ar an áit ina d'fhéach muid díreach. Bhí a fhios againn go raibh an lár ró-ard, nó an sprioc a bhí níos lú ná an lár, agus mar sin ní mór é a bheith ann, má tá sé ann ar chor ar bith sa eagar, áit éigin ar an taobh clé den lárphointe. Agus mar sin beidh orainn a leagtar ar an eagar suíomh díreach ar an taobh clé lárphointe mar an pointe deiridh nua. Go contrártha, má tá an sprioc níos mó ná cad atá ag an lár, a dhéanann muid mar an gcéanna cruinn phróiseas, ach ina ionad sin táimid ag athrú ar an pointe tosaigh a bheith díreach do cheart an lárphointe ríomh muid díreach. Agus ansin, muid ag cur tús leis an bpróiseas arís. A ligean ar a shamhlú seo, ceart go leor? Mar sin níl a lán ar siúl agus ar anseo, ach anseo tá sraith de na 15-eilimintí. Agus táimid ag dul a bheith súil a choinneáil de stuif lán níos mó an am seo. Mar sin, i cuardaigh líneach, bhí muid ach ag tabhairt aire faoi sprioc. Ach an uair seo ba mhaith linn a cúram faoi áit a bhfuil muid ag tosú chun breathnú, i gcás ina á stopadh táimid ag lorg, agus cad é an lárphointe an eagar atá ann faoi láthair. Mar sin anseo táimid ag dul leis cuardaigh dénártha. Táimid go leor i bhfad mhaith chun dul, ceart? Tá mé ag dul díreach a chur síos thíos anseo sraith de innéacsanna. Sé seo go bunúsach ach cad eilimint an eagar tá muid ag caint faoi. Le cuardach líneach, táimid ag cúram, sa mhéid agus muid Ní mór go mbeadh a fhios cé mhéad eilimintí táimid ag iterating os a chionn, ach ní dhéanaimid cúram i ndáiríre cad eilimint táimid ag lorg faoi láthair ag. Sa tóir dénártha, a dhéanann muid. Agus mar sin iad siúd ach ann mar threoir beag. Mar sin, is féidir linn tús, ceart? Bhuel, ní leor. Cuimhneamh ar cad a dúirt mé faoi ​​cuardaigh dénártha? Ní féidir linn é a dhéanamh ar eagar neamhshórtáilte nó eile, nach bhfuil muid ag ráthú go bhfuil na Níl eilimintí nó luachanna ar leith á thaisme discarded nuair muid díreach cinneadh a dhéanamh neamhaird a dhéanamh ar leath de na eagar. Mar sin, céim amháin le cuardaigh dénártha Is ní mór duit raon curtha in eagar. Agus is féidir leat é a úsáid aon cheann de na sórtáil halgartaim againn Labhair faoi a leat a fháil chun an phoist sin. Mar sin anois, tá muid i riocht ina is féidir linn a dhéanamh cuardaigh dénártha. Mar sin, a ligean ar arís ar an bpróiseas céim ar chéim agus a choinneáil súil a choinneáil ar cad atá ag tarlú mar a théann muid. Mar sin, an chéad gá dúinn a dhéanamh ná a ríomh an lárphointe an eagar atá ann faoi láthair. Bhuel, beidh orainn a rá go bhfuil muid, ar an gcéad go léir, ag lorg an luach 19. Táimid ag iarraidh a fháil ar an uimhir 19. An chéad eilimint den Tá eagar lonnaithe ag innéacs náid, agus an ghné dheireanach den Tá eagar lonnaithe ag innéacs 14. Agus mar sin beidh muid ag glaoch sin tús agus deireadh. Mar sin, táimid a ríomh an lárphointe ag ag cur 0 móide 14 roinnt ar 2; lárphointe deas simplí. Agus is féidir linn a rá go Is é an lárphointe anois 7. Mar sin, tá 15 cad tá muid ag lorg? Níl, tá sé nach bhfuil. Táimid ag lorg 19. Ach tá a fhios againn go bhfuil 19 níos mó ná an méid a fuair muid ar an lár. Mar sin, cad is féidir linn a dhéanamh ná athrú ar an pointe tosaigh a bheith díreach do cheart an lárphointe, agus arís ar an bpróiseas arís. Agus nuair a dhéanann muid go bhfuil, a rá againn anois ar an Tá pointe tús nua suíomh eagar 8. Cad atá déanta againn go héifeachtach é gach rud neamhaird ar an taobh clé de 15. Táimid tar éis a dhíchur leath na faidhbe, agus anois, in ionad a bheith chun cuardach a os cionn 15 eilimintí i ár sraith, ní mór dúinn ach chun cuardach a níos mó ná 7. Mar sin, tá 8 an pointe tosaigh nua. Is 14 fós ar an pointe deiridh. Agus anois, théann muid thar an arís. Ríomhaimid an lárphointe nua. 8 móide 14 Tá 22, arna roinnt ar 11 2. An é seo cad tá muid ag lorg? Níl, tá sé nach bhfuil. Táimid ag lorg luach go níos lú ná an méid a fuair muid díreach. Mar sin, táimid ag dul a dhéanamh arís an próiseas arís. Táimid ag dul a athrú ar an pointe deiridh a a bheith díreach ar an taobh clé den lárphointe. Mar sin, éiríonn an pointe deiridh nua 10. Agus anois, tá go an chuid amháin de an eagar ní mór dúinn a shórtáil tríd. Mar sin, ní mór dúinn a dhíchur anois 12 de na 15-eilimintí. Tá a fhios againn go bhfuil más rud é 19 ann sa eagar, sé Ní mór a bheith ann áit éigin idir eilimint uimhir 8 agus eilimint uimhir 10. Mar sin, linn a ríomh an lárphointe nua arís. 8 móide 10 18, arna roinnt ar 2 9. Agus sa chás seo, breathnú, an Is é sprioc ag an lár. Fuair ​​muid díreach cad tá muid ag lorg. Is féidir linn a stopadh. Curtha i gcrích go rathúil cuardaigh dénártha. Ceart go leor. Mar sin, tá a fhios againn an algartam Oibríonn má tá an sprioc áit éigin taobh istigh de na eagar. An bhfuil an obair algartam má nach bhfuil an sprioc sa eagar? Bhuel, a ligean ar tús a chur air arís, agus an uair seo, a ligean ar breathnú ar an eilimint 16, a amhairc féidir linn a fheiceáil gan a bheith ann áit ar bith ar an eagar. Is é an pointe tosaigh arís 0. Is é an pointe deiridh arís 14. Sin iad na innéacsanna de na chéad agus gnéithe deireanach ar an sraith iomlán. Agus beidh muid ag dul tríd an bpróiseas againn ach chuaigh tríd arís, ag iarraidh a fháil 16, cé amhairc, is féidir linn cheana insint nach bhfuil sé ag dul a bheith ann. Ba mhaith linn ach chun a chinntiú ar an algartam Beidh, go deimhin, fós ag obair ar bhealach éigin agus ní hamháin dúinn a fhágáil bhfostú i lúb gan teorainn. Mar sin, cad é an chéad chéim ar dtús? Ríomh an lárphointe an eagar atá ann faoi láthair. Cad é an lárphointe na eagar atá ann faoi láthair? Bhuel, tá sé 7, ceart? 14 móide 0 roinnt ar 2 7. 15 cad tá muid ag lorg? Uimh Tá sé deas gar, ach táimid ag lorg le haghaidh luach beagán níos mó ná sin. Mar sin, tá a fhios againn go bhfuil sé ag dul go dtí a bheith áit ar bith ar an taobh clé de 15. Is é an sprioc níos mó ná cad atá i lárphointe. Agus mar sin a leag muid an pointe tosaigh nua chun a bheith díreach do cheart an lár. Is é an lárphointe láthair 7, mar sin ligean le rá go bhfuil an pointe tosaigh nua 8. Agus cad tá muid go héifeachtach rinneadh arís é neamhaird an leath clé iomlán an eagar. Anois, arís againn ar an phróiseáil amháin níos mó ama. Ríomh an lárphointe nua. 8 móide 14 Tá 22, arna roinnt ar 11 2. Is 23 cad tá muid ag lorg? Ar an drochuair, uimh. Táimid ag lorg luach go bhfuil níos lú ná 23. Agus mar sin sa chás seo, táimid ag dul a athrú ar an pointe deiridh a bheith díreach ar an taobh clé den lárphointe reatha. Is é an lárphointe atá ann faoi láthair 11, agus mar sin beidh orainn a leagtar ar an pointe deiridh nua don chéad uair eile a théann muid tríd an bpróiseas seo go dtí 10. Arís, théann muid tríd an bpróiseas arís. Ríomh an lárphointe. 8 móide 10 roinnt ar 2 9. Is 19 cad tá muid ag lorg? Ar an drochuair, uimh. Táimid ag lorg i gcónaí le haghaidh uimhir níos lú ná sin. Mar sin, beidh linn a athrú ar an pointe deiridh an uair seo a bheith díreach ar an taobh clé den lárphointe. Is é an lárphointe láthair 9, mar sin beidh an pointe deiridh a bheith 8. Agus anois, tá muid ag lorg ach ag raon eilimint amháin. Cad é an lárphointe seo eagar? Bhuel, a thosaíonn sé ag 8, sé chríochnaíonn ar 8, is é an lárphointe 8. An é sin cad tá muid ag lorg? Táimid ag lorg 17? Níl, tá muid ag lorg 16. Mar sin, má tá sé ann sa eagar, ní mór é a bheith ann áit éigin an taobh clé de áit a bhfuil muid i láthair na huaire. Mar sin, cad tá muid ag dul a dhéanamh? Bhuel, beidh orainn a leagtar ar an pointe deiridh a bheith díreach ar an taobh clé den lárphointe reatha. Mar sin beidh orainn a athrú ar an pointe deiridh go 7. An bhfuil tú a fheiceáil cad go díreach a tharla anseo, cé? Féach suas anseo anois. Tá Tosaigh anois níos mó ná deireadh. Go héifeachtach, an dá foircinn dár sraith a thrasnaigh, agus is é an pointe tosaigh anois tar éis an pointe deiridh. Bhuel, ní dhéanann sin dhéanamh ar aon chiall, ceart? Mar sin anois, tá an méid is féidir linn a rá linn a go mbeadh fo sraith de mhéid 0. Agus nuair a tá muid ag gotten a an bpointe seo, is féidir linn anois ráthaíocht a thabhairt go eilimint 16 gan a bheith ann sa eagar, mar gheall ar an pointe tosaigh agus tá pointe deiridh thrasnaigh. Agus mar sin nach bhfuil sé ann. Anois, faoi deara go bhfuil sé seo beagán éagsúla ná an pointe tosaigh agus deiridh pointe a bheith mar an gcéanna. Dá mbeadh muid ag iarraidh ar feadh 17, bheadh ​​sé curtha sa eagar, agus an pointe tosaigh agus pointe deiridh an atriall caite roimh na pointí thrasnaigh, ba mhaith linn a fuair 17 ann. Tá sé ach amháin nuair a thrasnaíonn siad gur féidir linn ráthú nach ndéanann an eilimint ann sa eagar. Mar sin, a ligean ar a ghlacadh a lán níos lú céimeanna seachas cuardaigh líneach. Sa chás is measa, bhí againn a roinnt suas liosta na n-eilimintí n arís agus arís eile i leath chun teacht ar an sprioc, bíodh sé mar gheall ar an eilimint sprioc Beidh áit éigin sa deireanach roinn, nó nach bhfuil sé ann ar chor ar bith. Mar sin, i gcás is measa, ní mór dúinn a scoilt suas na array-- bhfuil a fhios agat? Logáil isteach na n-amanna n; táimid ag a ghearradh ar an bhfadhb i leath líon áirithe na n-amanna. Is é sin roinnt uaireanta logáil n. Cad é an scéal chás is fearr? Bhuel, an chéad uair táimid ag ríomh an lárphointe, feicimid cad tá muid ag lorg. I ngach na roimhe seo samplaí ar cuardaigh dénártha tá muid imithe díreach os cionn, má bhí againn ag lorg eilimint 15, ba mhaith linn a fuarthas amach go láithreach. Go raibh ag an tús an-. Ba é sin an lárphointe an chéad iarracht ag scoilt de rannán i cuardaigh dénártha. Agus mar sin i an ceann is measa cás, ritheann cuardaigh dhénártha i logáil n, atá i bhfad níos fearr ná cuardaigh líneach, sa chás is measa. Sa chás is fearr, dénártha Ritheann cuardaigh óimige de 1. Dá bhrí sin tá cuardach dénártha ar a lán níos fearr ná cuardaigh líneach, ach tá tú chun déileáil leis an bpróiseas sórtáil do eagar chéad uair roimh is féidir leat ghiaráil an chumhacht de cuardaigh dénártha. Tá mé Doug Lloyd. Is é seo an CS 50.