>> ROB BOWDEN: Hi, Im 'Rob.
Sut ydym yn cyflogi chwiliad deuaidd?
Gadewch i ni gael gwybod.
Felly, yn nodi bod chwiliad hwn rydym yn mynd i weithredu recursively.
Gallech hefyd yn gweithredu chwiliad deuaidd iteraidd, felly os ydych yn gwneud hynny,
mae hynny'n berffaith iawn.
>> Nawr yn gyntaf, gadewch i ni gofio yr hyn y mae'r paramedrau i chwilio yn cael eu golygu i fod.
Yma, rydym yn gweld gwerth int, sy'n i fod i fod yn y gwerth y mae'r defnyddiwr yn
chwilio am.
Rydym yn gweld yr amrywiaeth gwerthoedd int, a oedd yn yn y casgliad yr ydym yn
chwilio am werth.
Ac rydym yn gweld int n, sy'n hyd ein amrywiaeth.
>> Yn awr, peth cyntaf yn gyntaf.
Rydym yn gwirio i weld os n hafal i 0, yn ac os felly byddwn yn dychwelyd ffug.
Dim ond Dyna dweud os oes gennym gwag amrywiaeth, gwerth yn amlwg heb fod mewn
amrywiaeth gwag, fel y gallwn ddychwelyd ffug.
>> Nawr, rydym mewn gwirionedd yn awyddus i wneud y deuaidd Chwilio yn rhan o chwiliad deuaidd.
Felly, rydym yn awyddus i ddod o hyd i'r canol elfen o amrywiaeth hwn.
Yma, rydym yn dweud canol yn dychwelyd n rhannu 2, gan fod yr elfen canol yn
mynd i fod hyd ein casgliad wedi'i rannu â 2.
Nawr rydym yn mynd i wirio i weld os yw'r elfen canol hafal gwerth rydym yn
chwilio am.
Felly os gwerthoedd canol hafal werth, rydym yn gallu dychwelyd yn wir ers i ni dod o hyd i'r
gwerth yn ein casgliad.
>> Ond os nad oedd hynny'n wir, erbyn hyn mae angen i ni wneud y dychweliadol
cam o'r chwiliad deuaidd.
Mae angen i ni chwilio naill ai i'r chwith y rhesi neu i'r
nghanol y rhesi.
Felly dyma, rydym yn dweud os gwerthoedd yn canol yn llai na gwerth, mae hynny'n golygu bod y gwerth
yn fwy na'r canol y rhesi.
Felly mae'n rhaid i werth fydd i'r dde o'r elfen yr ydym newydd edrych ar.
>> Felly dyma, rydym yn mynd i chwilio recursively.
A byddwn yn edrych ar yr hyn rydym yn pasio i hyn mewn eiliad.
Ond rydym yn mynd i chwilio i'r dde o'r elfen canol.
Ac yn yr achos arall, mae hynny'n golygu bod gwerth yn llai na chanol y
amrywiaeth, ac felly rydym yn mynd i chwilio ar y chwith.
Yn awr, y chwith yn mynd i fod ychydig yn haws i edrych ar.
Felly, rydym yn gweld yma ein bod ni'n recursively galw chwiliad lle cyntaf
ddadl yw, unwaith eto, mae'r gwerth rydym yn edrych drosodd.
Yr ail ddadl yn mynd i fod y amrywiaeth ein bod yn chwilio drosodd.
A'r elfen olaf yn awr yw canol.
Cofiwch y paramedr olaf yw ein int n, felly dyna hyd ein amrywiaeth.
>> Yn yr alwad ailadroddus i chwilio, rydym yn ei ddweud yn awr bod hyd y
amrywiaeth yn canol.
Felly, os yw ein amrywiaeth oedd o faint 20 ac rydym yn chwilio am mynegai 10, gan fod canol yn
20 wedi'i rannu â 2, mae hynny'n golygu ein bod fynd heibio 10 gan fod y newydd
hyd ein amrywiaeth.
Cofiwch, pan fyddwch yn cael amrywiaeth hyd 10, mae hynny'n golygu y dilys
elfennau mewn mynegeion 0 i 9.
Felly, mae hyn yn union yr hyn yr ydym am ei nodi ein amrywiaeth yn ddiweddar - y chwith
amrywiaeth o'r elfen canol.
>> Felly, gan edrych i'r dde yn ychydig yn fwy anodd.
Nawr yn gyntaf, gadewch i ni ystyried hyd y rhesi ar y dde o'r
elfen canol.
Felly, os yw ein amrywiaeth oedd o faint n, yna bydd y Bydd casgliad newydd fod o faint n minws
minws canol 1.
Felly, gadewch i ni feddwl n canol minws.
>> Unwaith eto, os yw'r casgliad yn o faint 20 a rydym yn rhannu â 2 i gael y canol,
felly mae'r canol yn 10, yna mae n minws canol yn mynd i roi i ni 10, felly 10
elfennau i'r dde o'r canol.
Ond mae gennym hefyd minws hwn 1, gan nad ydym am i
gynnwys y canol ei hun.
Felly, n llai canol minws 1 yn rhoi i ni y cyfanswm nifer o elfennau i'r dde
o'r mynegai canol yn y rhesi.
>> Nawr dyma, cofiwch fod y canol paramedr yn yr amrywiaeth gwerthoedd.
Felly dyma, rydym yn basio amrywiaeth gwerthoedd diweddaru.
Mae hyn yn ogystal â gwerthoedd plws canol 1 yn mewn gwirionedd yn dweud recursively ffoniwch
chwilio, gan fynd heibio mewn amrywiaeth newydd, lle y casgliad newydd yn dechrau yn y canol
ynghyd ag un o'n gwerthoedd amrywiaeth gwreiddiol.
>> Mae cystrawen arall am hynny, nawr bod ydych wedi dechrau i weld awgrymiadau, yn
gwerthoedd ampersand yn ogystal canol 1.
Felly, chrafangia 'r cyfeiriad y canol ynghyd ag un elfen o werthoedd.
>> Yn awr, os nad ydych yn gyfforddus addasu amrywiaeth fel 'na, rydych yn
gallai hefyd wedi gweithredu hyn drwy ddefnyddio swyddogaeth cynorthwy-ydd ailadroddus, lle
swyddogaeth honno cynorthwy-ydd yn cymryd mwy o ddadleuon.
Felly, yn lle cymryd dim ond y gwerth, mae'r amrywiaeth, a maint y rhesi,
gallai'r swyddogaeth cynorthwy-ydd gymryd mwy o dadleuon, gan gynnwys y mynegai isaf
y byddech yn gofalu amdanynt yn y casgliad a'r mynegai uchaf yr ydych yn gofalu
am y rhesi.
>> Ac felly cadw golwg ar y isaf mynegai a'r mynegai uchaf, nad ydych yn
angen i addasu erioed gwerthoedd gwreiddiol arae.
Alli jyst barhau i defnyddio'r amrywiaeth gwerthoedd.
Ond yma, sylwch nad oes angen cynorthwy-ydd i ni weithredu cyhyd ag y byddwn yn
yn barod i addasu'r gwreiddiol gwerthoedd amrywiaeth.
Rydym yn barod i basio yn yn gwerthoedd diweddaru.
>> Nawr, ni allwn chwiliad deuaidd dros amrywiaeth sy'n heb eu didoli.
Felly, gadewch i ni ddatrys hyn.
Yn awr, yn sylwi bod math heibio dau paramedrau int gwerthoedd, sef y
amrywiaeth ein bod yn didoli, a int n, sef hyd y rhesi a
rydym yn didoli.
Felly, yma rydym yn awyddus i weithredu algorithm didoli
hynny yw o n sgwâr.
Gallech ddewis math swigen, dewis fath, neu fath gosod, neu
rhyw fath arall nid ydym wedi gweld yn y dosbarth.
Ond yma, rydyn ni'n mynd i ddefnyddio'r math dethol.
>> Felly, rydym yn mynd i ailadrodd dros yr amrywiaeth cyfan.
Wel, dyma ni yn gweld ein bod yn bwysleisio'r o 0 i n minws 1.
Beth am yr holl ffordd i fyny at n?
Wel, os ydym eisoes wedi datrys y cyntaf n minws 1 Elfennau, yna bydd y
elfen olaf hyn y mae'n rhaid fod yn barod yn y lle cywir, felly trefnu dros
yr amrywiaeth cyfan.
>> Yn awr, cofio sut dethol fath yn gweithio.
Rydym yn mynd i fynd dros y casgliad cyfan chwilio am y gwerth lleiaf mewn
yr amrywiaeth a ffon sy'n ar y dechrau.
Yna, rydym yn mynd i fynd dros y cyfan amrywiaeth eto yn chwilio am yr ail
elfen lleiaf, a ffon sy'n yn yr ail safle yn y
amrywiaeth, ac yn y blaen.
Felly, dyna beth mae hyn yn ei wneud.
>> Yma, rydym yn gweld ein bod ni'n gosod isafswm ar hyn o bryd
gwerth at y mynegai i-fed.
Felly, ar y iteriad cyntaf, rydym yn mynd i ystyried y gwerth lleiaf i fod yn
y dechrau ein amrywiaeth.
Yna, rydym yn mynd i ailadrodd dros y gweddill y rhesi, gwirio i
weld a oes unrhyw elfennau llai yno nag yr un yr ydym yn hyn o bryd
ystyried y lleiaf.
>> Felly dyma, yn rhoi gwerth j ac un - mae hynny'n yn llai na'r hyn yr ydym ar hyn o bryd
ystyried y lleiaf.
Yna, rydym yn mynd i ddiweddaru pa yn ein barn ni yw'r lleiafswm i
mynegai j plws 1.
Felly, yn gwneud hynny ar draws yr amrywiaeth cyfan, ac ar ôl hyn ar gyfer dolen, isafswm
Dylai fod yn elfen lleiaf o y sefyllfa i-fed yn y rhesi.
>> Unwaith y byddwn wedi hynny, gallwn gyfnewid y isafswm gwerth i mewn i'r sefyllfa i-fed
yn y rhesi.
Felly, mae hyn yn unig yw cyfnewid safonol.
Rydym yn cadw mewn gwerth dros dro - i-fed gwerth yn yr arae -
rhoi yn y i-fed gwerth yn yr arae y gwerth isafswm sy'n perthyn yno,
ac yna'i storio yn ôl i lle mae'r gwerth lleiaf cyfredol a ddefnyddir i fod yn
i-fed gwerth yn yr arae, felly na wnaethom golli.
>> Felly, mae hynny'n parhau ar y fersiwn nesaf.
Byddwn yn dechrau chwilio am yr ail gwerth lleiaf a rhowch hynny yn y
ail safle.
Ar y trydydd ailadroddiad, byddwn yn edrych am y trydydd gwerth lleiaf a mewnosoder
hynny yn y trydydd safle, ac yn y blaen ymlaen nes gennym amrywiaeth ddidoli.
Fy enw i yw Rob, ac mae hyn yn Roedd fath dethol.