[CHWARAE CERDDORIAETH] 

DOUG LLOYD: Pob hawl. Felly chwiliad deuaidd yn algorithm gallwn ddefnyddio i ddod o hyd elfen y tu mewn o amrywiaeth. Yn wahanol i chwilio llinol, mae'n gofyn am yn cael eu bodloni amod arbennig ymlaen llaw, ond mae'n llawer mwy effeithlon os bod cyflwr yw, mewn gwirionedd, wedi cyfarfod. 

Felly beth yw'r syniad yma? 'i' rhaniad a gorchfygu. Rydym yn awyddus i leihau maint yr ardal chwilio hanner bob tro er mwyn dod o hyd i rif darged. Dyma lle y cyflwr yn dod i chwarae, er. Ni allwn ond trosoledd grym dileu hanner yr elfennau heb hyd yn oed edrych ar iddynt os y casgliad yn cael ei datrys. 

Os mai cymysgedd cyflawn i fyny, ni allwn yn unig allan o law taflu hanner o'r elfennau, gan fod nid ydym yn gwybod beth rydym yn taflu. Ond os bydd yr amrywiaeth yn cael eu didoli, gallwn wneud hynny, oherwydd ein yn gwybod bod popeth i'r chwith lle'r ydym ar hyn o bryd Mae'n rhaid i fod yn is na'r gwerth yr ydym yn hyn o bryd ar. Ac mae popeth i'r cywir o'n sefyllfa Mae'n rhaid i fod yn fwy na'r gwerth Ar hyn o bryd rydym yn edrych ar. 

Felly beth yw'r pseudocode camau ar gyfer chwilio deuaidd? Rydym yn ailadrodd y broses hon nes bod y array neu, wrth i ni symud ymlaen drwy, is-araeau, darnau llai o yr amrywiaeth gwreiddiol, o faint 0. Cyfrifwch y man canol o'r is amrywiaeth cyfredol. 

Os yw gwerth yr ydych yn chwilio amdano yw yn yr elfen honno y rhesi, rhoi'r gorau. Rydych yn ei chael yn. Mae hynny'n wych. Fel arall, os yw'r targed yn llai na'r hyn sydd yn y canol, felly os bydd y gwerth yr ydym yn chwilio am yn is na'r hyn a welwn, ailadrodd y broses hon eto, ond newid y pwynt diwedd, yn lle hynny o fod y gwreiddiol cwblhau amrywiaeth llawn, i fod yr un ar y chwith o ble yr ydym newydd edrych. 

Rydym yn gwybod bod y canol yn rhy uchel, neu y targed yn llai na'r canol, ac felly mae'n rhaid iddo fodoli, os yw'n yn bodoli o gwbl yn y array, rhywle i ochr chwith y man canol. Ac felly byddwn yn gosod y rhesi Lleoliad ychydig i'r chwith y man canol fel y man pen newydd. I'r gwrthwyneb, os yw'r targed fwy na'r hyn sydd yn y canol, rydym yn ei wneud yr union un fath broses, ond yn lle hynny rydym newid y man cychwyn i fod yn ychydig i'r dde o'r man canol rydym yn unig cyfrifo. Ac yna, rydym yn dechrau ar y broses eto. 

Gadewch i ddychmygu hyn, OK? Felly mae llawer yn digwydd ac ar fan hyn, ond dyma amrywiaeth o'r 15 elfen. Ac rydym yn mynd i fod yn cadw golwg o lot mwy o stwff y tro hwn. Felly, yn chwilio llinol, roeddem dim ond gofalu am darged. Ond y tro hwn rydym am poeni am ble rydym ni dechrau edrych, lle a ydym yn rhoi'r gorau i chwilio, a beth yw'r man canol y rhesi ar hyn o bryd. Felly dyma ni gyda chwiliad deuaidd. Rydym yn 'n bert lawer da i fynd, dde? Im 'jyst yn mynd i roi i lawr islaw fan set o fynegeion. Mae hyn yn y bôn yn unig pa elfen y rhesi rydym yn sôn am. Gyda chwiliad llinol, rydym yn gofal, yn gymmaint ag i ni angen gwybod faint o elfennau rydym yn ailadrodd drosodd, ond nid ydym yn poeni mewn gwirionedd beth elfen o bryd rydym yn edrych ar. Yn chwilio deuaidd, rydym yn ei wneud. Ac felly y rhai yn unig yno cyn lleied canllaw. 

Er mwyn i ni ddechrau, dde? Wel, nid yn eithaf. Cofiwch yr hyn a ddywedais am chwilio deuaidd? Ni allwn wneud hynny ar amrywiaeth heb eu didoli neu fel arall, nid ydym yn gwarantu bod y Nid yw elfennau neu werthoedd penodol yn cael eu yn ddamweiniol taflu pan rydym yn unig penderfynu anwybyddu hanner y rhesi. 

Felly cam un gyda chwiliad deuaidd yn rhaid i chi gael amrywiaeth didoli. A gallwch ddefnyddio unrhyw un o'r didoli algorithmau rydym wedi siarad am i fynd â chi i'r sefyllfa honno. Felly nawr, rydym mewn sefyllfa lle gallwn berfformio chwiliad deuaidd. 

Felly gadewch i ni ailadrodd y broses gam wrth gam a chadw golwg ar yr hyn sy'n digwydd wrth i ni fynd. Felly, y tro cyntaf mae angen i ni ei wneud yw cyfrifo bwynt canol y casgliad ar hyn o bryd. Wel, byddwn yn dweud ein bod, yn gyntaf i gyd, yn chwilio am y gwerth 19. Rydym yn ceisio dod o hyd i'r rhif 19. Yr elfen gyntaf y arae wedi ei lleoli yn fynegai sero, a'r elfen olaf y arae ei leoli yn fynegai 14. Ac felly byddwn yn galw rhai sy'n dechrau a diwedd. 

Felly, rydym yn cyfrifo y man canol gan gan ychwanegu 0 plws 14 wedi'i rannu â 2; canolbwynt eithaf syml. Ac gallwn ddweud bod y man canol yn awr 7. Felly, yn 15 yr hyn rydym yn chwilio amdano? Na, nid yw'n. Rydym yn chwilio am 19. Ond rydym yn gwybod bod 19 yn fwy na'r hyn a welsom yn y canol. 

Felly, yr hyn y gallwn ei wneud yw newid y man cychwyn i fod ychydig i'r dde o'r pwynt canol, ac ailadrodd y broses eto. A phan yr ydym yn gwneud hynny, yr ydym yn awr yn dweud y man cychwyn newydd yn lleoliad arae 8. Beth rydym wedi'i wneud yn effeithiol yn popeth hanwybyddu ar ochr chwith y 15. Rydym wedi dileu hanner o'r broblem, ac yn awr, yn hytrach na gorfod chwilio dros 15 elfen yn ein array, Dim ond rhaid i ni chwilio dros 7. Felly 8 yw'r man cychwyn newydd. 14 yn dal i fod y pwynt diwedd. 

Ac yn awr, yr ydym yn mynd dros hyn eto. Rydym yn cyfrifo'r man canol newydd. 8 plws 14 yw 22, wedi'i rannu â 2 yw 11. A yw hyn yn yr hyn rydym yn chwilio amdano? Na, nid yw'n. Rydym yn chwilio am werth sy'n yn llai na'r hyn yr ydym newydd o hyd. Felly rydym yn mynd i ailadrodd y broses eto. Rydym yn mynd i newid y pwynt diwedd i fod ychydig i'r chwith o'r man canol. Felly, y pwynt pen newydd yn dod yn 10. Ac yn awr, dyna'r unig ran o yr amrywiaeth mae'n rhaid i ni ddatrys drwy'r. Felly, rydym yn awr wedi dileu 12 o'r 15 elfen. Rydym yn gwybod, os 19 yn bodoli yn y array, mae'n Mae'n rhaid i fodoli rhywle rhwng yr elfen rhif 8 a rhif yr elfen 10. 

Felly, rydym yn cyfrifo'r man canol newydd eto. 8 a 10 yw 18, wedi'i rannu â 2 yw 9. Ac yn yr achos hwn, edrych, y targed ar y canol. Gwelsom yn union yr hyn rydym yn chwilio amdano. Gallwn roi'r gorau iddi. Rydym yn cwblhau'n llwyddiannus chwiliad deuaidd. Iawn. Felly, rydym yn gwybod algorithm hwn yn gweithio os yw'r targed rhywle y tu mewn y rhesi. A yw hyn yn gweithio algorithm os nad yw'r targed yn y arae? Wel, gadewch i ni ddechrau ei unwaith eto, a'r tro hwn, gadewch i ni edrych ar gyfer yr elfen 16, sy'n weledol gallwn weld yn bodoli yn unrhyw le yn y rhesi. 

Y pwynt cychwyn unwaith eto 0. Y pwynt pen unwaith eto 14. Dyna'r mynegeion o'r cyntaf ac elfennau olaf y rhesi cyflawn. A byddwn yn mynd drwy'r broses rydym yn unig Aeth drwy'r eto, ceisio dod o hyd 16, hyd yn oed er eu golwg, y gallwn eisoes dweud nad yw'n mynd i fod yno. Rydym yn unig am wneud yn siŵr algorithm hwn Bydd, mewn gwirionedd, yn dal i weithio mewn rhyw ffordd ac nid dim ond yn ein gadael sownd mewn dolen ddiddiwedd. 

Felly, beth yw'r cam cyntaf? Cyfrifwch y man canol y rhesi ar hyn o bryd. Beth yw'r man canol y rhesi ar hyn o bryd? Wel, mae'n 7, dde? 14 plws 0 rannu â 2 yw 7. Yw 15 yr hyn rydym yn chwilio amdano? Na Mae'n eithaf agos, ond rydym yn edrych am werth ychydig yn fwy na hynny. 

Felly, rydym yn gwybod ei fod yn mynd i yn unman i'r chwith o'r 15. Y targed yn fwy na beth sydd yn y man canol. Ac felly rydym yn gosod y man cychwyn newydd i fod ychydig i'r dde o'r canol. Mae'r canolbwynt ar hyn o bryd 7, felly gadewch i ni ddweud y man cychwyn newydd yw 8. A beth rydym wedi effeithiol wneud eto yn cael ei anwybyddu y cyfan hanner chwith y rhesi. 

Nawr, rydym yn ailadrodd y prosesu un mwy o amser. Cyfrifwch y man canol newydd. 8 plws 14 yw 22, wedi'i rannu â 2 yw 11. A yw 23 yr hyn rydym yn chwilio amdano? Yn anffodus, dim. Rydym yn chwilio am werth sy'n llai na 23. Ac felly yn yr achos hwn, rydym yn mynd i newid y pwynt diwedd i fod yr un i'r chwith y man canol ar hyn o bryd. Mae'r canolbwynt ar hyn o bryd yw 11, ac felly byddwn yn gosod y pwynt pen newydd am y tro nesaf rydym yn mynd drwy'r broses hon i 10. 

Unwaith eto, rydym yn mynd drwy'r broses unwaith eto. Cyfrifwch y man canol. 8 a 10 wedi'i rannu â 2 yw 9. A yw 19 yr hyn rydym yn chwilio amdano? Yn anffodus, dim. Rydym yn dal i chwilio am nifer llai na hynny. Felly, byddwn yn newid y diweddbwynt y tro hwn i fod ychydig i'r chwith o'r man canol. Mae'r canolbwynt ar 9 ar hyn o bryd, felly bydd y pwynt diwedd fod yn 8. Ac yn awr, rydym yn unig yn chwilio yn elfen amrywiaeth sengl. 

Beth yw pwynt canol yn arae hon? Wel, mae'n dechrau am 8, mae'n yn dod i ben yn 8, mae'r man canol yw 8. A yw bod yr hyn yr ydym yn chwilio amdano? A ydym yn chwilio am 17? Na, rydym yn chwilio am 16. Felly, os yw'n bodoli yn y casgliad, rhaid iddo fodoli rhywle i'r chwith o'r lle yr ydym ar hyn o bryd yn cael eu. Felly, beth ydym yn mynd i'w wneud? Wel, byddwn yn gosod y pwynt diwedd i fod yr un i'r chwith y man canol ar hyn o bryd. Felly, byddwn yn newid y pwynt diwedd i 7. A ydych yn gweld beth yn union ddigwyddodd yma, er bod? Chwiliwch am yma nawr. 

Start yn awr yn fwy na diwedd. I bob pwrpas, mae'r ddau yn dod i ben o'n array wedi croesi, a'r man cychwyn yw yn awr ar ôl y pwynt diwedd. Wel, nid yn gwneud hynny yn gwneud unrhyw synnwyr, dde? Felly nawr, yr hyn y gallwn ei ddweud yw ein bod cael amrywiaeth o is-maint 0. Ac unwaith y byddwn ni'n gotten i y pwynt hwn, y gallwn yn awr warantu y elfen 16 yn bodoli yn y casgliad, am fod y man cychwyn a phwynt diwedd wedi croesi. Ac felly nid yw'n yno. Yn awr, yn sylwi bod hyn ychydig yn yn wahanol na'r pwynt dechrau a diwedd pwyntio yr un fath. Os ydym wedi bod yn edrych am 17, byddai'n cael bod yn y array, a'r man cychwyn a phwynt diwedd y iteriad diwethaf cyn pwyntiau hynny groesi, byddem wedi dod o hyd 17 yno. Dim ond pan fyddant yn croesi y gallwn gwarantu nad yw'r elfen yn yn bodoli yn y rhesi. 

Felly gadewch i ni gymryd llawer llai o camau nag chwiliad llinol. Yn y sefyllfa waethaf, roedd gennym i rannu rhestr o elfennau n dro ar ôl tro yn ei hanner i ddod o hyd i'r targed, naill ai oherwydd yr elfen targed Bydd yn rhywle yn yr olaf rhannu, neu nid yw'n bodoli o gwbl. Felly, yn yr achos gwaethaf, mae'n rhaid i ni gwahanu y array-- ydych chi'n gwybod? Log amseroedd n; rydym rhaid i dorri y broblem yn ei hanner nifer penodol o weithiau. Bod nifer o weithiau yn log n. 

Beth yw'r senario achos gorau? Wel, yr ydym tro cyntaf cyfrifwch y man canol, rydym yn dod o hyd yr hyn rydym yn chwilio amdano. Ym mhob un o'r blaenorol enghreifftiau ar chwilio deuaidd rydym newydd mynd dros, os oedd gennym bod yn chwilio am yr elfen 15, byddem wedi canfod bod ar unwaith. Dyna oedd ar y dechrau. Dyna oedd canolbwynt y cynnig cyntaf ar raniad o is-adran i chwilio deuaidd. 

Ac felly yn y gwaethaf achos, chwilio deuaidd yn rhedeg yn n log, sy'n sylweddol well na chwilio llinol, yn yr achos gwaethaf. Yn yr achos gorau, deuaidd chwilio rhedeg mewn omega o 1. Felly chwiliad deuaidd yn llawer yn well na chwilio llinol, ond rhaid i chi ddelio â'r broses o didoli eich array gyntaf cyn y gallwch trosoledd grym chwiliad deuaidd. 

Rwy'n Doug Lloyd. Mae hyn yn CS 50.