Yurttas/PL/OOL/Cplusplus/F/05/04/03/00/binary search.cpp

 1/*
 2   Copyright(C) 2002
 3   All Rights Reserved. Salih Yurttas, ZCubes, BitsOfCode Software Systems, Inc..
 4
 5   Permission to use, copy, modify, and distribute this
 6   software and its documentation for EDUCATIONAL purposes
 7   and without fee is hereby granted provided that this
 8   copyright notice appears in all copies.
 9
10   date   : January 1, 2002.
11   author : Salih Yurttas.
12
13   binary_search.cpp
14*/
15
16
17#include <vector>
18
19using namespace std;
20
21template <class T>
22bool binary_search(T key,
23                   vector<T>& list) {
24  bool found = false;
25
26  int low = 0;
27  int high = list.size();
28
29  int mid;
30
31  while(low<=high&&!found) {
32    mid = low+(high-low)/2;
33    if(key==list[mid])
34      found = true;         /* found it!             */
35    else if(key<list[mid])
36      high = mid-1;         /* search the lower part */
37    else               
38      low = mid+1;          /* search the upper part */
39  }
40  return found;
41}