Searching an Array

The list of names below is sorted into alphabetical order. When we search an ordered list, we can write a much more efficient search. For an ordered list, you can use a binary search.

index names years
0Amy2010
1 Bill1985
2 Debbie1976
3 Ian1987
4 Jay1974
5 Josh2003
6 Lin2009
7 Mark1979
8 Paul2001

We will use the same program that read in the names from a file, but instead of a sequential search, we will use a binary search.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//Input a list of names and year born from file
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int readfile(string names[],int years[],int max) {
  int count=0;
  ifstream namefile;  //input file stream
  namefile.open("c:/mycpp/names2.txt"); //associates the name with a file
  if (namefile.fail()) //maybe no disk in external file, or the file does not exist
    cout<<"File not found\n"; //cout is used to notify user of error
  else  {
    while(!namefile.eof() && count<max) {
      namefile>>names[count];
      namefile>>years[count];
      count++;
    } //while
  } //file ok
  return count;
}//readfile
int bsearch(string names[], string name, int size) {
  int min=0;
  int max=size-1;
  int pos;
  int found=-1;
  while(min<=max && found==-1) {
    pos=(min+max)/2; //midpoint of the range
    if(name==names[pos]) found=pos;
    else if(name<names[pos]) max=pos-1;
    else min=pos+1;
  }
  return found;
}

void main()
{ string names[20];
  int years[20];
  int size;
  string lookfor;
  size=readfile(names,years,20);
  cout<<"Enter the name of the person you are looking for:";
  getline(cin,lookfor);
  int pos;
  pos=bsearch(names,lookfor,size);
  if(pos>=0) cout<<lookfor<<" was born in "<<years[pos]<<endl;
  else cout<<lookfor<<" was not found.\n";
  system("pause");
} //main
CODE
When you test this program make sure you test for the first and last person, someone who is not there before and after the names and somewhere in the middle.

NEXT: A number guessing game