Kif jaħdem il-binary search, u x'jirrikjedi?

Question

Accepted Answer

**Il-binary search** isib il-mira f'array **imsortiż** billi nqas il-firxa ta' search bil-nofs ripetutament. Kull paraguni jneħħi nuss mill-elementi li jifdal, u tagħti ħin ta' **O(log n)**. ## L-idea Tħares il-element tan-nofs. Jekk huwa ugwali mal-mira, inti lesta. Jekk il-mira hija iżgħar, fittex in-nofs tax-xellug; jekk ikbar, fittex in-nofs tal-lemin. Repeti sakemm sib jew il-firxa tkun vojta. ## Eżempju ```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 ``` ## Traċċa ```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 ``` ## Kumplessità - **Ħin:** O(log n). **Spazju:** O(1) iterattiv. ## Ħoŧot **Il-input għandu jkun imsortiż** — inkella r-riżultati huma bla sens. Ħo ħsieb minn bugs off-by-one f'`lo`/`hi` u overflow ta' interi fi ħafna lingwi (uża `lo + (hi-lo)//2`). ## Għaliex Huwa Importanti Nqas il-firza tan-nofs jibdel tfittxija ta' miljun element għal madwar 20 paraguni. Il-mudell divide-and-conquer wara jidher mill-ġdid f'siġar, databases, u problemi ta' intervista bla għadd. L-għarfien tal-uniku rekwiżit rigorużu tiegħu — input imsortiż — iħalllik protett minn bug sottili klassiku.