બાઈનરી શોધ - એક સૌથી સરળ રીતે એક એરે માં એક તત્વ શોધવા માટે

તદ્દન ઘણીવાર પ્રોગ્રામરો, પણ શરૂઆત હકીકતમાં નંબરો સમૂહ, કે જે ચોક્કસ નંબર શોધવા જ જોઈએ છે કે ત્યાં હતો. તે આ સંગ્રહમાં ઝાકઝમાળ કહેવામાં આવે છે. અને તે વસ્તુઓ શોધવા માટે, ત્યાં રીતે અસંખ્ય છે. પરંતુ તેમાંના મોટા ભાગના સરળ જમણી બાજુ પર દ્વિસંગી શોધ ગણી શકાય. શું આ પદ્ધતિ છે? અને કેવી રીતે દ્વિસંગી શોધ અમલ કરવા? પાસ્કલ આવા કાર્યક્રમ સંસ્થા માટે સૌથી સહેલો પર્યાવરણ છે, તેથી અમે તેને ઉપયોગ કરશો અભ્યાસ કરવો.

પ્રથમ, વિશ્લેષણ, આ પદ્ધતિ ફાયદા શું છે, તે છે કે જેથી અમે સમજીએ છીએ કરી શકો છો, વિષય અભ્યાસમાં બિંદુ શું છે. તો, ચાલો ઓછામાં ઓછા 100000000 તત્વો, કેટલાક શોધવાની જરૂર જે પરિમાણ સાથે ઝાકઝમાળ હોય દો. અલબત્ત, આ સમસ્યા સરળતાથી એક સરળ રેખીય શોધ, જેમાં આપણે ચક્ર ઉપયોગ કરી રહ્યા છો તે બધા એરે માં છે જરૂરી તત્વ તુલના દ્વારા ઉકેલી શકાય છે. સમસ્યા એ છે કે આ વિચારનો અમલ ખૂબ સમય લાગી શકે છે. અનેક સારવાર, અને મુખ્ય લખાણ ત્રણ લીટીઓમાં એક સરળ પાસ્કલ કાર્યક્રમમાં, તો તમે તેને નોટિસ નહીં, પરંતુ જ્યારે અમે શાખાઓ અને સારા કાર્યક્ષમતા મોટી સંખ્યામાં સાથે વધુ અથવા ઓછા મોટા પ્રોજેક્ટ પર આવે છે, કાર્યક્રમ પણ લાંબા સમય માટે લોડ કરવા તૈયાર થઈ જશે. ખાસ કરીને જો કોમ્પ્યુટર નબળા પ્રદર્શન છે. તેથી, ત્યાં એક દ્વિસંગી શોધ છે, જે શોધ સમય ઓછામાં ઓછા બે વાર ઘટાડો કરે છે.

તેથી, આ પદ્ધતિ કામ સિદ્ધાંત શું છે? તરત જ તેને કહેવું જોઈએ કે દ્વિસંગી શોધ કામ કરે છે કોઈપણ એરે નથી, પરંતુ માત્ર નંબરોની છટણી સેટ પર. દરેક પગલું ભર્યું એરે મધ્યમાં તત્વ અંતે (તત્વ સંખ્યા જેનો અર્થ). જરૂરી હોય તો સંખ્યા કરતાં વધારે હોય છે સરેરાશ, પછી બાકી છે કે બધા છે, કે સરેરાશ સેલ કરતાં ઓછી છે, છોડવામાં કરી શકાય છે અને ત્યાં જોવા નથી. તેનાથી વિપરીત, જો સરેરાશ કરતાં ઓછી - જમણે તે નંબરો વચ્ચે, તમે શોધવા શકતા નથી. તો પછી જ્યાં પ્રથમ તત્વ સમગ્ર એરે મધ્યમાં તત્વ, અને છેલ્લા અને છેલ્લા હશે એક નવું શોધ વિસ્તાર, પસંદ કરો. નવું ક્ષેત્ર સરેરાશ સંખ્યા બધા સેગમેન્ટમાં છે કે, (છેલ્લું તત્વ હતું + સમગ્ર એરે મધ્યમાં તત્વ) / 2 ¼ હશે. ફરીથી, આ જ કામગીરી કરવામાં આવે છે - અરે સરેરાશ સંખ્યા સાથે તુલના. જો લક્ષ્ય મૂલ્ય સરેરાશ કરતાં ઓછી છે, અમે જમણી બાજુ નકારવા અને તે પણ ત્યાં સુધી હવે આ મધ્યમ તત્વ ઇચ્છિત ન હોત આગામી કરવું.

અલબત્ત, તે કેવી રીતે દ્વિસંગી શોધ લખી એક ઉદાહરણ જોવા શ્રેષ્ઠ છે. પાસ્કલ અહીં કોઈને અનુકૂળ રહેશે - આવૃત્તિ મહત્વની નથી. ચાલો એક સરળ પ્રોગ્રામ લખવા દો.

તે નામ "massiv" હેઠળ એચ 1 ઝાકઝમાળ છે, ચલ શોધ નીચલા સીમા સૂચવે છે, "niz" કહેવાય છે, ઉચ્ચ મર્યાદા, "verh", સરેરાશ શોધ શબ્દ કહેવાય - "sredn"; અને જરૂરી નંબર - "isk".

તેથી, પ્રથમ અમે શ્રેણી શોધ ઉપલા અને નીચલા મર્યાદા સોંપી:

niz = 1;
verh = H + 1;

પછી ચક્ર આયોજન "સુધી નીચે ઉચ્ચ મર્યાદા કરતાં ઓછી છે":

niz શરૂ

દરેક પગલું ખાતે, અમે સેગમેન્ટમાં 2 વિભાજીત:

sredn: = (niz + verh) div 2; {કાર્ય div વાપરો, કારણ કે બાકીની વગર વિભાજન}

સમીક્ષા દરેક સમય. કારણ કે આઇટમ પહેલેથી જો મધ્યમ ઇચ્છિત છે મળી આવી છે, વિક્ષેપિત સાયકલ:

જો sredn = isk પછી તોડી;

એરે મધ્યમાં તત્વ ઇચ્છિત કરતાં વધુ, ડાબી બાજુ કાઢી તો તે છે, સરેરાશ ઉપલા સીમા નિમણૂક તત્વ:

જો massiv [sredn]> isk પછી verh = sredn;

અને વિપરીત પર, તો તે નીચલી સીમા બનાવે છે:

બીજું niz = sredn;
અંત;

તે બધા કાર્યક્રમ હશે છે.

અમને ધ્યાનમાં તે વ્યવહારમાં દ્વિસંગી પદ્ધતિ જોવા મળશે કેવી રીતે કરીએ. આ એરે પર ધ્યાન આપો: 1, 3, 5, 7, 10, 12, 18 અને તે નંબર 12 લેવી પડશે.

કુલ અમે 7 તત્વો હોય છે, તેથી ચોથા મધ્યમ, કિંમત 7 કરશે.

12, 7, 1.3 કરતાં વધુ અને 5 તત્વો હોવાથી, અમે કાઢી શકો છો. પછી અમે નંબર 4 મેળવ્યું, 4/2 કોઈ અવશેષ 2. તેથી, એક નવી તત્વ 10 ની એવરેજ હશે.

ત્યારથી 12 10 કરતા વધારે છે, અમે 7. માત્ર 10, 12 અને 18 રહે કાઢી નાખો.

અહીં, મધ્યમ તત્વ પહેલેથી 12 છે, તે જરૂરી નંબર છે. આ કાર્ય પૂર્ણ થાય છે - નંબર 12 મળી.