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}