Binary nrhiav - ib qho ntawm qhov uas yooj yim txoj kev mus nrhiav lub caij nyob rau hauv ib tug array

Heev feem ntau, programmers, txawm beginners, kev nyuaj siab nrog lub fact tias muaj yog ib tug txheej ntawm cov zauv, uas yuav tsum nrhiav ib txog kev xov tooj. Nws yog ib qhov sau yog hu ua ib tug array. Thiab mus nrhiav khoom nyob rau hauv nws, muaj ntau lub myriad ntawm txoj kev. Tab sis feem ntau yooj yim ntawm lawv yuav suav hais tias ib tug binary nrhiav nyob rau txoj cai. Yuav ua li cas yog cov qauv no yog? Thiab yuav ua li cas los mus siv binary nrhiav? Pascal yog ib qho yooj yim ib puag ncig rau lub koom haum ntawm xws li ib tug kev pab cuam, ces peb mam li siv nws los kawm.

Ua ntej, tsom xam, dab tsi yog qhov zoo ntawm no txoj kev, nws yog li ntawd peb yuav to taub, dab tsi yog qhov point nyob rau hauv txoj kev tshawb no ntawm lub npe. Yog li ntawd, peb muaj ib tug array nrog ib tug dimension ntawm tsawg kawg yog 100000000 hais, uas yuav tsum tau mus nrhiav tau ib co. Ntawm cov hoob kawm, qhov teeb meem no yuav muab tau yooj yim daws tau los ntawm ib tug yooj yim linear search, nyob rau hauv uas peb siv lub voj voog yuav piv qhov yuav tsum tau caij nrog tag nrho cov uas yog nyob rau hauv lub array. Qhov teeb meem no yog hais tias qhov kev siv ntawm cov tswv yim no yuav muab sij hawm ntau heev. Nyob rau hauv ib tug yooj yim Pascal kev pab cuam mus rau hauv ob peb txoj kev kho mob, thiab peb kab ntawm lub ntsiab ntawv nyeem, koj yuav tsis pom nws, tab sis thaum peb tuaj mus rau ib tug ntau dua los yog tsawg loj tej yaam num nrog ib tug loj tus naj npawb ntawm cov ceg ntoo thiab zoo functionality, qhov kev pab cuam yuav tsum npaj txhij yuav loaded mus ntev ntev. Tshwj xeeb tshaj yog yog hais tias tus computer yog ib tug tsis muaj zog ua tau zoo. Yog li ntawd, muaj ib tug binary search, uas thiaj li nrhiav sij hawm tsawg kawg yog ob zaug.

Yog li ntawd, dab tsi yog cov ua hauj lwm hauv paus ntsiab lus ntawm no txoj kev? Tam sim ntawd nws yuav tsum hais tias binary nrhiav hauj lwm yog tsis nyob rau hauv tej array, tiam sis tsuas yog rau ib tug sorted set ntawm cov zauv. Nyob rau txhua kauj ruam coj nruab nrab lub caij ntawm lub array (lub ntsiab lus hauv lub xov tooj ntawm lub caij). Yog hais tias yuav tsum tau muaj ntau dua qhov nruab nrab, ces txhua yam uas yog sab laug, uas yog tsawg tshaj li qhov nruab nrab ntawm tes, muaj peev xwm muab pov tseg thiab tsis txhob saib muaj. Conversely, yog hais tsawg tshaj li qhov nruab nrab - ntawm cov xov tooj mus rau sab xis, koj yuav tsis nrhiav. Ces xaiv ib tug tshiab kev tshawb fawb hauv cheeb tsam, qhov chaw uas thawj lub caij yuav hauv nruab nrab lub caij ntawm tag nrho array, thiab lub xeem thiab lub xeem nyiam. Qhov nruab nrab pes tsawg tus tshiab teb yuav ¼ ntawm tag nrho cov ya, hais tias yog, (lub xeem caij + rau hauv nruab nrab lub caij ntawm tag nrho array) / 2. Ib zaug ntxiv, tib yam hauj lwm yog ua - ib tug sib piv nrog qhov nruab nrab ntawm lub array. Yog hais tias lub hom phiaj tus nqi yog tsawg tshaj li qhov nruab nrab, peb tsis kam ua rau sab xis, thiab kuj yuav ua tom ntej no, kom txog rau thaum tam sim no no hauv nruab nrab lub caij yuav tsis xav.

Ntawm cov hoob kawm, nws yog ib qhov zoo tshaj plaws rau saib ib qho piv txwv ntawm yuav ua li cas sau ntawv binary nrhiav. Pascal no yuav nplua leej twg - version yog tsis tseem ceeb. Wb sau ib tug yooj yim kev pab cuam.

Nws yog ib qho array ntawm 1 mus rau h nyob rau hauv lub npe "massiv", ib tug nce mus nce los ntawm lub sab ciam ntawm cov kev tshawb fawb, hu ua "niz", lub sab sauv txwv, hu ua "verh", qhov nruab nrab lub sij hawm nrhiav - "sredn"; thiab yuav tsum tau tooj - "isk".

Yog li ntawd, ua ntej peb muab lub Upper thiab qis tsis pub tshaj ntawm lub ntau yam kev tshawb fawb:

niz: = 1;
verh: = h + 1;

Ces npaj lub voj voog "kom txog thaum lub qab yog tsawg tshaj li tus sab sauv txwv":

Thaum niz pib

Nyob rau txhua kauj ruam, peb tau faib cov ya 2:

sredn: = (niz + verh) div 2; {Siv cov nuj nqi div, vim hais tias cov sib faib tsis seem}

Txhua lub sij hawm ntawm kev ntsuam xyuas. Vim hais tias cov khoom tau twb tau pom tias qhov nruab nrab yog qhov kev kawm, cuam tshuam voj voog:

іf sredn = isk ces tawg;

Yog hais tias qhov nruab nrab lub caij ntawm lub array ntau tshaj kev kawm, muab pov tseg rau sab laug, uas yog, lub sab sauv ciam ntawm qhov nruab nrab taw caij:

yog massiv [sredn]> isk ces verh: = sredn;

Thiab yog hais tias nyob rau hauv qhov tsis tooj, nws yuav ua rau lub sab ciam:

lwm niz: = sredn;
xaus;

Hais tias yog tag nrho hais tias yuav muaj nyob rau hauv qhov kev pab cuam.

Cia peb xav txog yuav ua li cas nws yuav zoo lub binary txoj kev nyob rau hauv xyaum. Xav txog qhov no array: 1, 3, 5, 7, 10, 12, 18 thiab nws yuav nrhiav tus xov tooj 12.

Nyob rau hauv tag nrho peb muaj 7 ntsiab, li ntawd, yuav cov plaub nruab nrab, cov nqi 7.

Txij li thaum ntau tshaj li 12, 7, 1.3 thiab 5 ntsiab, peb yuav muab pov tseg. Tom qab ntawd peb twb tau txais cov xov tooj 4, 4/2 tsis muaj residue yog 2. Yog li ntawd, ib tug tshiab lub caij yuav ua tau ib tug nruab nrab ntawm 10.

Txij li thaum 12 yog ntau tshaj 10, peb muab pov tseg 7. tseem tsuas 10, 12 thiab 18.

Ntawm no, rau hauv nruab nrab lub caij no twb yog 12, nws yog ib qhov yuav tsum tau tus xov tooj. Qhov no ua hauj lwm yog ua tiav - cov 12 pom.