Si funksionon kërkimi binar dhe çfarë kërkon?

Question

Accepted Answer

**Kërkimi binar** gjen një objektiv në një masiv **të sortuar** duke përgjysmuar në mënyrë të përsëritur intervalin e kërkimit. Çdo krahasim eliminon gjysmën e elementeve të mbetura, duke dhënë **O(log n)** kohë. ## Ideja Shikoni elementin e mesit. Nëse barazohet me objektivin, përfundim. Nëse objektivi është më i vogël, kërkoni në gjysmën e majtë; nëse është më i madh, kërkoni në gjysmën e djathtë. Përsëritni derisa të gjendet ose intervali është bosh. ## Shembull ```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 ``` ## Gjurmim ```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 ``` ## Kompleksitet - **Kohë:** O(log n). **Hapësirë:** O(1) përsëritës. ## Grackat **Hyrja duhet të jetë e sortuar** — përndryshe rezultatet janë pa kuptim. Ruajuni gabimeve off-by-one në `lo`/`hi` dhe tejmbushjes të numrit të plotë në disa gjuhë (përdorni `lo + (hi-lo)//2`). ## Pse është e rëndësishme Përgjiysma e hapësirës së kërkimit e kthen kërkimin në një masiv me një milion elementesh në ~20 krahasime. Mostra e ndaj-dhe-sundoj pas saj shfaqet sërish në pemë, baza të dhënash dhe pafundësisht shumë probleme interviste. Dija e kërkesës së tij të vetme të vështirë — hyrja e sortuar — ju mban larg një gabimi klasik të hollë.