Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap

binary search

You are here: irt.org | FOLDOC | binary search

<algorithm> A search algorithm which repeatedly divides an ordered search space in half according to how the required (key) value compares with the middle element.

The following pseudo-C routine performs a binary search return the index of the element of vector "thing[first..last]" equal to "target":

 if (target < thing[first] || target > thing[last])
   return NOT_FOUND;
 while (first < last)
   mid = (first+last)/2;	/* truncate to integer */
   if (target == thing[mid])
     return mid;
   if (target < thing[mid])
     last = mid-1;
     first = mid+1;
 if (target == thing[last])
   return last;
 return NOT_FOUND;


Nearby terms: binary large object « binary package « binary prefix « binary search » Binary Synchronous Transmission » binary tree » BIND

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL

©2018 Martin Webb