બાઈનરી સર્ચ કેવી રીતે કામ કરે છે, અને તેને શું જરૂરી છે?

Question

Accepted Answer

**Binary search** **સાજેલ** એરેમાં ટার્ગેટ શોધે છે, સર્ચ શ્રેણીને વારંવાર અર્ધેણી કરીને। દરેક સરખામણી બાકીના અડધા તત્વોને દૂર કરે છે, **O(log n)** સમય આપે છે। ## વિચાર મધ્યમ તત્વ તરફ જુઓ. જો તે ટાર્ગેટ સમાન હોય તો કરી ગયા. જો ટાર્ગેટ નાનું હોય તો ડાબી અર્ધ સર્ચ કરો; જો મોટું હોય તો જમણી અર્ધ સર્ચ કરો. જ્યાં સુધી મળે નહીં અથવા શ્રેણી ખાલી ન થાય ત્યાં સુધી પુનરાવર્તન કરો। ## ઉદાહરણ ```python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 # middle index if arr[mid] == target: return mid # found it elif arr[mid] < target: lo = mid + 1 # discard left half else: hi = mid - 1 # discard right half return -1 # not present binary_search([1, 3, 5, 7, 9], 7) # -> 3 ``` ## ટ્રેસ ```text Search 7 in [1,3,5,7,9] lo=0 hi=4 mid=2 -> 5 < 7 => lo=3 lo=3 hi=4 mid=3 -> 7 == 7 => return 3 ``` ## જટિલતા - **સમય:** O(log n). **જગ્યા:** O(1) પુનરાવર્તીય. ## મુશ્કેલીઓ **ઇનપુટ સાજેલું હોવું જોઈએ** — અન્યથા પરિણામો અર્થહીન છે. `lo`/`hi` માં ઓફ-બાય-વન બગને ધ્યાનમાં રાખો અને કેટલીક ભાષાઓમાં પૂર્ણાંક ઓવરફ્લો (આ `lo + (hi-lo)//2` વાપરો). ## શા માટે તે મહત્વપૂર્ણ છે સર્ચ સ્પેસને અર્ધવચન કરવાથી મિલિયન-તત્વ શોધ ~20 સરખામણીમાં બદલાય છે. તેની પાછળનું વિભાજન-અને-જીત પેટર્ન વૃક્ષો, ડેટાબેસ અને અસંખ્ય ઇન્ટરવ્યુ સમસ્યાઓમાં પુનરાવર્તિત થાય છે. તેની એક કઠોર આવશ્યકતા — સાજેલું ઇનપુટ — જાણવું ક્લાસિક સૂક્ષ્મ બગથી બચાવે છે.