Searching an Array

We would like to search an unsorted list such as the one below for a particular name. We will use a sequential search because the list is not sorted.

index names years
0 Jay 1974
1 Debbie 1976
2 John 1918
3 Greg 1954
4 Carol 2011
5 Sam 2000
     
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
49
50
51
//Read in name and year born from a file into a vector
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
int getFile(string names[],int yearBorn[]) {
  int count=0;
  string input,yearString;
  ifstream people("c:/mycpp/names2.txt"); //input file stream
  if(people) { //file was opened
    while(getline(people,input)) { //Example: input="Jay,1994" 
      int p=input.find_first_of(","); //Example: p=3 
      if(p>=0) {
        names[count]=input.substr(0,p); //Example: name="Jay"
        yearString=input.substr(p+1); // Example: yearString="1994"
        yearBorn[count]=stoi(yearString); //stoi=String To Int, Example: yearBorn=1994
        count++;
      }//there was a comma
    }//each line
    people.close(); 
  }
  return count;
}//getFile

int search(string names[], string name, int size) {
  int found=-1;
  int i=0;
  while(found<0 && i<size) {
    if(names[i]==name) found=i;
    i++;
  }
  return found;
}//search

int main(void) {
  string names[20], lookfor;
  int yearborn[20],age,count=0;
  count=getFile(names,yearborn);
  if(count==0) cout<<"There was an error reading the file.\n";
  else {
    cout<<count<<" people read\n";
    cout<<"Enter the name of the person you are looking for:";
    getline(cin,lookfor);
    int pos;
    pos=search(names,lookfor,count);
    if(pos>=0) cout<<lookfor<<" was born in "<<yearborn[pos]<<endl;
    else cout<<lookfor<<" was not found.\n";
  }
  system("pause");
  return 0;
} //main 
CODE

Notice that although there is room in the array for 20 people, there are only 6 in this particular file. We must always pass the number of actual records to the search.

A sequential search of N records will find an existing name in about N/2 tries. Sometimes the name will be at the beginning, sometimes at the end, but on average the number of tries will be about half the size of the array.

If the name we are looking for is not on the list, we must search the entire list (N tries) to determine that the person is not found.

NEXT: A Binary Search