Binary search aimsíonn sprioc i raun dhraíochta tríd an raon cuardaigh a leathú arís is arís eile. Díchuimsiú leath de na heilimintí fágtha le gach comparáid, rud a thugann O(log n) am.
Féach ar an eilimint lár. Má bhíonn sé cothrom leis an sprioc, déantar é. Má tá an sprioc níos lú, cuardaigh an leathchuid chlé; má tá sé níos mó, cuardaigh an leathchuid dheas. Athdhéan go dtí go bhfaighfidh tú é nó go mbeidh an raon folamh.
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
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
Caithfidh an ionchur a bheith raun — ar a shéan tá na torthaí gan ciall. Aire a dhéanamh ar bhuanna as aon taobh in lo/hi agus sreabadh slánuimhir i roinnt teangacha (úsáid lo + (hi-lo)//2).
Léim go leith an spás cuardaigh a thaitin go 20 comparáid in áit milliún eilimint.
An patrún deighilt-is-dul-ar-aghaidh taobh thiar de atáirgeadh i gcrainn, bunachar sonraí, agus a lán fhadhbanna agallamh.
Bheith ar eolas ar a aon riachtanas crua — ionchur raun — coigiltí gus fabht clasaiceach agus soiléir.