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])
      last = mid;
    else if (target > thing[mid])
      first = mid+1;
    else
      return mid;
  }
  if (target == thing[last])
    return last;
  return NOT_FOUND;