[સંગીત વગાડવાનો] 

ડો LLOYD: બધા અધિકાર. તેથી દ્વિસંગી શોધ એક છે અમે ઉપયોગ કરી શકો છો અલ્ગોરિધમનો એક એરે અંદર એક તત્વ શોધવા માટે. રેખીય શોધ વિપરીત, તે માટે જરૂરી છે એક ખાસ શરત અગાઉથી મળવી પરંતુ તે વધુ કાર્યક્ષમ તો છે શરત છે કે, હકીકતમાં, મળ્યા હતા. 

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

તે એક સંપૂર્ણ મિશ્રણ છે, તો અમે હમણાં જ હાથ બહાર નથી કરી શકો છો કારણ કે, આ તત્વો અડધા કાઢી અમે કાઢી રહ્યાં છે તે ખબર નથી. પરંતુ એરે છટણી કરવામાં આવે તો અમે તે કરી શકો છો કારણ કે અમે માટે બધું છે કે જે ખબર અમે હાલમાં છે જ્યાં બાકી આ કરતાં ઓછી હોવી જ જોઈએ કિંમત અમે હાલમાં છો. અને બધું કરવા માટે જ્યાં અમે છે અધિકાર કિંમત કરતાં મોટી હોવી જ જોઈએ અમે હાલમાં અંતે શોધી રહ્યાં છે. 

તેથી સ્યુડોકોડનો શું છે દ્વિસંગી શોધ માટે પગલાંઓ? અમે ત્યાં સુધી આ પ્રક્રિયા પુનરાવર્તન એરે અથવા, અમે મારફતે આગળ વધવા, પેટા એરે, નાના ટુકડાઓ મૂળ એરે કદ 0 છે. મિડપોઇન્ટ ગણતરી વર્તમાન પેટા એરે છે. 

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

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

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

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

તેથી દ્વિસંગી શોધ સાથે એક પગલું તમે એક છટણી એરે હોવી જ જોઈએ. અને તમે સૉર્ટ કોઈપણ ઉપયોગ કરી શકો છો અમે વિશે વાત કરી ગાણિતીક નિયમો તે સ્થિતિમાં તમે વિચાર. તેથી હવે, અમે એક પદ જ્યાં છો અમે દ્વિસંગી શોધ કરી શકો છો. 

તેથી આ પ્રક્રિયા પુનરાવર્તન દો પગલું દ્વારા પગલું અને રાખવા અમે જાઓ તરીકે ચાલી રહ્યું છે તે ટ્રેક. તેથી પ્રથમ અમે ગણતરી કરવાની જરૂર છે વર્તમાન એરે મિડપોઇન્ટ. વેલ, અમે પ્રથમ, અમે છો કહેવું પડશે બધા, કિંમત 19 માટે જોઈ. અમે નંબર 19 શોધવા માટે પ્રયાસ કરી રહ્યાં છો. આ પ્રથમ તત્વ અરે, અનુક્રમણિકા શૂન્ય પર સ્થિત થયેલ છે અને આ છેલ્લા તત્વ અરે ઇન્ડેક્સ 14 પર સ્થિત છે. અને તેથી અમે તે શરૂઆત અને અંત કહી શકશો. 

તેથી અમે મિડપોઇન્ટ દ્વારા ગણતરી 0 વત્તા 2 દ્વારા વિભાજી 14 ઉમેરવાનું; ખૂબ સરળ મિડપોઇન્ટ. અને અમે કહી શકો છો મિડપોઇન્ટ હવે 7 છે. તેથી 15 અમે શોધી રહ્યાં છો શું છે? ના, તે નથી. અમે 19 માટે શોધી રહ્યાં છે. પરંતુ અમે 19 વધારે ખબર છે કે અમે મધ્યમ પર મળી છે તેના કરતાં. 

તેથી અમે શું કરી શકો છે શરૂઆત બિંદુ જ બદલી માત્ર જમણી હોઈ મિડપોઇન્ટ, અને ફરીથી પ્રક્રિયા પુનરાવર્તન કરો. અમે તે કરવા જ્યારે, આપણે હવે કહે છે નવી શરૂઆત બિંદુ એરે સ્થાન 8 છે. શું અમે અસરકારક રીતે કર્યું છે 15 ડાબી અવગણવામાં બધું. અમે અડધા દૂર કર્યું આ સમસ્યા, અને હવે, તેના બદલે શોધ કર્યા અમારા એરે 15 તત્વો, અમે માત્ર 7 શોધવા માટે છે. 8 નવા શરૂ બિંદુ છે. 14 હજુ પણ અંત બિંદુ છે. 

અને હવે, અમે ફરી આ પર જાઓ. અમે નવા મિડપોઇન્ટ ગણતરી. 8 વત્તા 14 2 11 દ્વારા વિભાજી, 22 છે. આ અમે શોધી રહ્યાં છો શું છે? ના, તે નથી. અમે છે કે કિંમત માટે જોઈ રહ્યાં છો, અમે હમણાં જ મળી છે તેના કરતાં ઓછો હોય છે. તેથી અમે પુનરાવર્તન કરવા જઈ રહ્યાં છો ફરીથી પ્રક્રિયા. અમે ઓવરને બિંદુ બદલવા જઈ રહ્યા છો ફક્ત મિડપોઇન્ટ ડાબી થાઓ. જેથી નવા ઓવરને બિંદુ 10 બની જાય છે. અને હવે, કે ના માત્ર ભાગ છે એરે અમે મારફતે સૉર્ટ હોય છે. તેથી અમે હવે દૂર કરવામાં આવી 15 તત્વો 12. આપણે જાણીએ છીએ કે જો 19 એરે અસ્તિત્વમાં છે, તે તત્વ વચ્ચે ક્યાંક અસ્તિત્વમાં હોવું જોઈએ નંબર 8 અને તત્વ નંબર 10. 

તેથી અમે ફરીથી નવા મિડપોઇન્ટ ગણતરી. 8 વત્તા 10 2 9 દ્વારા વિભાજી, 18 છે. અને આ કિસ્સામાં, આ જુઓ લક્ષ્ય મધ્યમાં છે. અમે શોધી રહ્યાં છો બરાબર શું જોવા મળે છે. અમે રોકી શકો છો. અમે સફળતાપૂર્વક પૂર્ણ દ્વિસંગી શોધ. બધા અધિકાર. તેથી અમે આ અલ્ગોરિધમનો ખબર લક્ષ્ય છે, તો કામ કરે છે ક્યાંક એરે અંદર. આ અલ્ગોરિધમનો કામ તો કરે છે લક્ષ્ય એરે નથી? વેલ, તે શરૂ કરીએ ફરી, અને આ સમય, માતાનો તત્વ જોવા દો દૃષ્ટિની અમે જોઈ શકો છો કે જે 16, એરે ક્યાંય અસ્તિત્વમાં નથી. 

આ શરૂ બિંદુ ફરી 0 હોય છે. ઓવરને બિંદુ ફરી 14 છે. તે પ્રથમ સૂચકાંક છે અને સંપૂર્ણ એરે છેલ્લા તત્વો છે. અને અમે આ પ્રક્રિયા આપણે માત્ર પસાર કરશો પસાર થયું ફરીથી, 16 શોધવા માટે પ્રયાસ કરી, પણ દૃષ્ટિની છતાં, અમે પહેલેથી જ કરી શકો છો તે ત્યાં નથી ચાલી રહ્યું છે કે જણાવો. અમે હમણાં જ ખાતરી કરો કે આ અલ્ગોરિધમનો બનાવવા માંગો છો હકીકતમાં, હજુ પણ અમુક રીતે કામ કરશે અને માત્ર અમને છોડી નથી એક અનંત લૂપ અટકી. 

તેથી આ પગલું પ્રથમ શું છે? મિડપોઇન્ટ ગણતરી વર્તમાન એરે છે. મિડપોઇન્ટ શું છે વર્તમાન એરે છે? વેલ, તે યોગ્ય, 7 છે? 2 દ્વારા વિભાજી 14 વત્તા 0 7 છે. અમે શોધી રહ્યાં છો તે 15 છે? નંબર તે ખૂબ નજીક છે, પરંતુ અમે શોધી રહ્યાં છો કરતાં સહેજ મોટા કિંમત માટે. 

તેથી અમે તે ચાલી રહ્યું છે ખબર છે કે 15 ડાબી ક્યાંય છે. લક્ષ્યાંક કરતાં વધારે છે શું મિડપોઇન્ટ છે. અને તેથી અમે નવા શરૂ બિંદુ સુયોજિત માત્ર મધ્યમાં જમણી છે. મિડપોઇન્ટ, જેથી હાલમાં 7 આપણે નવા શરૂ બિંદુ છે 8 કહે છે. અને અમે અસરકારક રીતે શું કર્યું ફરીથી થાય અવગણવામાં આવે છે એરે સમગ્ર ડાબી અડધા. 

હવે, આપણે પુનરાવર્તન વધુ એક વખત પ્રક્રિયા કરે છે. નવી મિડપોઇન્ટ ગણતરી. 8 વત્તા 14 2 11 દ્વારા વિભાજી, 22 છે. અમે શોધી રહ્યાં છો તે 23 છે? કમનસીબે, કોઈ. અમે કિંમત માટે જોઈ રહ્યાં છો, કે 23 કરતાં ઓછી છે. અને તેથી આ કિસ્સામાં, અમે જઈ રહ્યાં છો ઓવરને બિંદુ બદલવા માટે માત્ર હોઈ વર્તમાન મિડપોઇન્ટ ડાબી. વર્તમાન મિડપોઇન્ટ 11 છે, અને તેથી અમે તેને નવા ઓવરને બિંદુ સેટ કરશો અમે જાઓ આગામી સમય માટે 10 આ પ્રક્રિયા દ્વારા. 

ફરીથી, અમે ફરીથી પ્રક્રિયા મારફતે જાઓ. મિડપોઇન્ટ ગણતરી. 2 દ્વારા વિભાજી 8 વત્તા 10 9 છે. અમે શોધી રહ્યાં છો તે 19 છે? કમનસીબે, કોઈ. અમે હજુ પણ શોધી રહ્યાં છો કરતા ઓછી સંખ્યા. તેથી અમે ઓવરને બિંદુ આ સમય બદલવા પડશે ફક્ત મિડપોઇન્ટ ડાબી હોય છે. મિડપોઇન્ટ હાલમાં 9 તેથી અંતિમ બિંદુ 8 હશે. અને હવે, અમે ફક્ત શોધી રહ્યાં છો એક તત્વ એરે છે. 

આ એરે મિડપોઇન્ટ શું છે? વેલ, તે, 8 પર શરૂ થાય છે 8 થાય છે, મિડપોઇન્ટ 8 છે. કે અમે શોધી રહ્યાં છો શું છે? અમે 17 માટે શોધી રહ્યાં છો? ના, અમે 16 શોધી રહ્યાં છે. તે એરે માં હાજર હોય તો, તે ક્યાંક અસ્તિત્વમાં હોવું જોઈએ અમે હાલમાં છે જ્યાં ડાબી. તેથી અમે શું કરવા જઇ રહ્યા છે? ઠીક છે, આપણે પ્રયત્ન ઓવરને બિંદુ સેટ કરશો વર્તમાન મિડપોઇન્ટ ડાબી. તેથી અમે 7 ઓવરને બિંદુ બદલવા પડશે. તમે શું માત્ર જોવા કરો છતાં, અહીં થયું? હવે અહીં જુઓ. 

પ્રારંભ હવે અંત કરતાં વધારે છે. અસરકારક રીતે, બે છેડા અમારા એરે ઓળંગી દીધી છે, અને પ્રારંભ બિંદુ છે હવે ઓવરને બિંદુ પછી. ઠીક છે, કે નથી અધિકાર, કોઈપણ અર્થમાં બનાવવા? તેથી હવે, અમે શું કહી શકો છો અમે છે કદ 0 એક પેટા એરે હોય છે. અને એક વાર અમે મેળવેલ કરી રહ્યાં છો આ બિંદુએ, અમે હવે આ કરી શકો છો તે તત્વ બાંયધરી 16 એરે અસ્તિત્વમાં નથી, આ શરૂ બિંદુ છે, કારણ કે અને ઓવરને બિંદુ ઓળંગી દીધી છે. અને તેથી તે ત્યાં નથી. હવે, આ સહેજ નોંધ્યું છે કે આ શરૂ બિંદુ અને અંતિમ કરતાં અલગ એ જ હોવા નિર્દેશ કરે છે. અમે જોઈ હોત તો 17, તે હશે એરે, અને પ્રારંભ બિંદુ કરવામાં આવી કે છેલ્લા પુનરાવૃત્તિ અને ઓવરને બિંદુ તે પોઇન્ટ પાર પહેલાં, આપણે ત્યાં 17 શક્યું હોત. તેઓ અમે કરી શકો છો કે પાર જ્યારે તે માત્ર તત્વ નથી કે ખાતરી આપી એરે અસ્તિત્વ ધરાવે છે. 

તેથી આપણે ખૂબ ઓછા લેવા દો રેખીય શોધ કરતાં પગલાંઓ. ખરાબ કેસ કિસ્સાઓમાં, અમે હતી n તત્વોના યાદી વિભાજિત વારંવાર અડધા, લક્ષ્ય શોધવા માટે ક્યાં છે, કારણ લક્ષ્ય તત્વ છેલ્લા ક્યાંક હશે વિભાગ, અથવા તે બધા અસ્તિત્વમાં નથી. સૌથી ખરાબ કિસ્સામાં તેથી, અમે છે તમે જાણો છો એરે વિભાજન? N વખત લોગ; અમે સમસ્યા કાપી છે વખત અડધા એક નિશ્ચિત સંખ્યા છે. વખત કે જે નંબર લોગ n છે. 

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

અને તેથી સૌથી ખરાબ કેસ, દ્વિસંગી શોધ ચાલે છે નોંધપાત્ર સારી છે, જે લોગ n છે, સૌથી ખરાબ કિસ્સામાં રેખીય શોધ કરતાં. શ્રેષ્ઠ કિસ્સામાં, દ્વિસંગી શોધ 1 ઓમેગા ચાલે છે. તેથી દ્વિસંગી શોધ ઘણો છે રેખીય શોધ કરતાં વધુ સારી, પરંતુ તમે આ પ્રક્રિયા સાથે વ્યવહાર હોય છે તમે કરી શકો છો પહેલાં પ્રથમ તમારા એરે સૉર્ટ દ્વિસંગી શોધ શક્તિ લાભ. 

હું ડો લોયડ છું. આ 50 સીએસ છે.