# Yellow Pages Search

I've written code in Free Pascal based on a contest problem (The contest insists that I have to write with Pascal). It works like charm, but I think it still need some improvements, from memory usage to runtime.

Input Format

First line is n (Number of people in the Yellow Pages) and q (Number of people to search) {1 <= n <= 10000} and {1 <= q <= 10000}

Next n lines are Yellow Pages entries, each line is the name and the phone number, space delimited. The name is uppercase letters with maximum length of 15, while the length of the phone number is exactly 7 digits.

Next q lines are the people to search, also in uppercase letters with maximum length 15.

Output Format

Output is q lines, where each line is the phone number of the people to search

Input Sample

10 5
AARON 8468431
BEN 1573457
GREGORY 1765743
JACK 3746843
JILL 1357891
MICHAEL 1375638
MONET 1357562
SHEILA 1378651
TERRY 8756345
YIN 1781945
GREGORY
YIN
AARON
MONET
JACK


Output Sample

1765743
1781945
8468431
1357562
3746843


My Code

program YellowPages;

type string7 = String[7];

var
namearray : Array of shortstring;
numberarray, searcharray : Array of string7;
input, name, search : shortstring;
number : string7;
n, q, iter1, iter2 : word;

procedure SplitInput(input : shortstring; var name : shortstring; var number : string7);
var
iter_proc, hitspace : byte;
begin
hitspace := pos(' ', input);
name := '';
number := '';
for iter_proc := 1 to length(input) do
begin
if iter_proc < hitspace then name := name + input[iter_proc];
if iter_proc > hitspace then number := number + input[iter_proc];
end;
end;

begin
setlength(namearray, n);
setlength(numberarray, n);
setlength(searcharray, q);
for iter1 := 0 to (n - 1) do
begin
SplitInput(input, name, number);
namearray[iter1] := name;
numberarray[iter1] := numberarray;
end;
for iter1 := 0 to (q - 1) do
begin
for iter2 := 0 to (n - 1) do
begin
if namearray[iter2] = search then break;
end;
searcharray[iter1] := numberarray[iter2];
end;
for iter1 := 0 to (q - 1) do
begin
writeln(searcharray[iter1]);
end;
end.


The first thing I would do is switch from using parallel arrays to using a single array of records. Create a record that holds both the name and the phone number of each person in the phonebook, like this:

Type
Contact = Record
name : shortstring;
number : String7;
end;


Once you've done that, you should sort the array based on each contact's name. The quicksort algorithm is fairly easy to implement and is usually quite fast in most cases.

Once you have the array sorted, instead of searching through the entire phonebook from the beginning, you can use a binary search to find each record you want and get the phone number from it. A binary search should never require more than log2(n) comparisons (where n is the size of the array you're searching). Whereas your search requires on average n/2 comparisons. So for 100 entries, you'd never perform more than ~8 comparisons with a binary search, whereas you'd usually do around 50 using a linear search.

I haven't used FreePascal or any other Pascal compiler in a long time. It's possible that they have some built-in sorting and searching procedures that you could use. But it's not hard to implement the ones mentioned above.

Also, in SplitInput() you're manually copying the data from one string to another. Usually there's a library with a procedure for copying a string or a part of a string. These will usually be faster than writing your own. (For example, in C you could use memcpy() or strncpy(). I'm not sure if there's an equivalent in Pascal.)

• I think I don't need quicksort, because the yellowpage entry input is already alphabetically ordered. – possibility0 Jun 3 '15 at 6:45
• Nice suggestion for the records. I've got SplitInput() updated to use Copy(). The only thing that bugs me is the binary search for the yellowpage record. Because the type to search is a string and the one doing comparing is an integer, I can't relate both. I'm considering doing an ord() check for the first character, but there will be names with same first character. What should I do? – possibility0 Jun 3 '15 at 6:53
• @RyoArmanda good point about not needing the sort. Phone books are already sorted! It turns out that Pascal directly supports string comparisons. So if you have a < b where a and b are strings, you'll get the correct answer. – user1118321 Jun 3 '15 at 15:52
• I didn't know about that, thanks! Binary search is a success. Any more tips? If no more tips, I'll wrap this code up nice. – possibility0 Jun 4 '15 at 6:49
• That's all I can think of at the moment. Good luck! – user1118321 Jun 4 '15 at 16:05