Binarju tfittxija - wieħed mill-modi eħfef biex isibu element fil-firxa

Spiss, programmaturi, anke jibdew, ffaċċjati bil-fatt li hemm sett ta 'numri, li jridu jsibu numru speċifiku. Huwa dan il-ġbir jissejjaħ firxa. U biex isibu oġġetti fiha, hemm numru kbir ta 'modi. Iżda l-aktar sempliċi ta 'minnhom jista' jitqies tfittxija binarja fuq il-lemin. X'inhu dan il-metodu hu? U kif għandhom jiġu implimentati tfittxija binarja? Pascal hija l-ambjent eħfef għall-organizzazzjoni ta 'tali programm, hekk aħna ser jużawha għall-istudju.

L-ewwel, tanalizza, x'inhuma l-vantaġġi ta 'dan il-metodu, huwa hekk nistgħu jifhmu, dak huwa l-punt fl-istudju tas-suġġett. Allura, ejja jkollhom firxa b'dimensjoni ta 'mill-inqas 100000000 elementi, li jeħtieġ li ssib xi. Naturalment, din il-problema jistgħu jissolvew faċilment minn tfittxija lineari sempliċi, li aħna qed jużaw iċ-ċiklu se tipparaguna l-element meħtieġ ma 'dawk kollha li huma fil-firxa. Il-problema hija li l-implimentazzjoni ta 'din l-idea se jieħu wisq żmien. Fi programm Pascal sempliċi f'diversi trattamenti, u tliet linji tat-test prinċipali, inti mhux ser avviż, iżda meta aħna jaslu għal proġetti ftit jew wisq kbar ma 'numru kbir ta' fergħat u l-funzjonalità tajba, il-programm se jkunu lesti biex jiġu mgħobbija għal ħin twil wisq. Speċjalment jekk il-kompjuter huwa prestazzjoni dgħajfa. Għalhekk, hemm tiftix binarju, li jnaqqas il-ħin tat-tiftix mill-inqas darbtejn.

Allura, x'inhu l-prinċipju ta 'ħidma ta' dan il-metodu? Immedjatament għandu jingħad li tfittxija binarju jaħdem huwa bl-ebda firxa, iżda biss fuq sett issortjati ta 'numri. F'kull pass meħud element nofs tal-firxa (jiġifieri l-għadd ta 'l-element). Jekk il meħtieġa numru huwa akbar mill -medja, allura kollha li jkun baqa ', li huwa inqas mill-ċellula medja, jistgħu jiġu skartati u mhux li tħares hemmhekk. Bil-maqlub, jekk inqas mill-medja - fost dawn in-numri fuq il-lemin, inti ma tistax tfittex. Imbagħad jagħżlu żona tfittxija ġdida, fejn l-ewwel element se jkun l-element nofs tal-firxa sħiħa, u l-aħħar u l-aħħar se. In-numru medju ta 'qasam ġdid se jkun ¼ ta' l-segment, jiġifieri, (l-aħħar element + l-element nofs tal-firxa sħiħa) / 2. Għal darb'oħra, l-istess operazzjoni hija mwettqa - paragun man-numru medju ta 'l-array. Jekk il-valur mira hija inqas mill-medja, aħna tirrifjuta-lemin, u wkoll tagħmel li jmiss, sa issa dan l-element tan-nofs ma tkunx mixtieqa.

Naturalment, huwa aħjar li wieħed iħares lejn eżempju ta 'kif jiktbu tfittxija binarja. Pascal hawnhekk se suit kulħadd - verżjoni mhix importanti. Ejja jikteb programm sempliċi.

Huwa firxa ta '1 sa h taħt l-isem "Massiv", varjabbli tindika l-konfini t'isfel tat-tfittxija, imsejħa "NIZ", il-limitu ta' fuq, imsejħa "verh", il-medja tfittxija terminu - "sredn"; u n-numru meħtieġ - "isk".

Allura, l-ewwel aħna jassenja l-limitu ta 'fuq u t'isfel tat-tfittxija firxa:

NIZ: = 1;
verh: = h + 1;

Imbagħad jorganizzaw iċ-ċiklu "sakemm il-qiegħ ikun anqas mil-limitu ta 'fuq":

Filwaqt NIZ tibda

F'kull pass, aħna jaqsam is-segment 2:

sredn: = (NIZ + verh) div 2; {Uża l-div funzjoni, minħabba li l-qasma mingħajr bqija}

Kull darba ta 'reviżjoni. Minħabba li l-oġġett ikun diġà ġie kkonstatat jekk il-mezz huwa mixtieq, jinterrompu ċiklu:

jekk sredn = isk allura break;

Jekk l-element nofs tal-firxa aktar minn mixtieq, armi fuq ix-xellug, jiġifieri, il-konfini ta 'fuq tal-medja jaħtar element:

jekk Massiv [sredn]> isk allura verh: = sredn;

U jekk għall-kuntrarju, jagħmel il-konfini t'isfel:

NIZ inkella: = sredn;
aħħarin;

Li kollox li se jkun fil-programm.

Ejjew jikkunsidraw kif se tfittex il-metodu binarja fil-prattika. Ikkunsidra dan firxa: 1, 3, 5, 7, 10, 12, 18 u se tfittex l-għadd 12.

B'kollox għandna 7 elementi, hekk se-raba medju, il-valur 7.

Peress li aktar minn 12, 7, 1.3 u 5 elementi, nistgħu jarmi. Imbagħad konna ltqajna l-numru 4, 4/2 ebda residwu huwa 2. Allura, element ġdid se jkun medja ta '10.

Mit-12 ta huwa ikbar minn 10, aħna jarmi 7. jibqa 'biss 10, 12 u 18.

Hawnhekk, l-element tan-nofs huwa diġà 12, huwa l-għadd meħtieġ. Dan il-kompitu huwa komplut - numru 12 misjuba.