Pascal guide - String-searching

the most simple one:
linear search:

linear search means searching datas/array one by one to find a target,
here are a sample of that:
sample 1:

var
 name:array [1..5] of string;
 k:integer;
 target:string;
begin
  name[1]:=John;name[2]:=susan;
  name[3]:=sam;name[4]:=mark;
  name[5]:=simpson;
 
  write('enter target name here:');
  readln(target);

  {linear searching}
  k:=0;
  repeat
   k:=k+1;
  until target=name[K];{checking for name[K]}
  if name[K]=target then
   writeln('target ',name[K],' find in array',K)
  else
   writeln('target not found');
 end.

 linear ordered search:
  linear orderd searching like linear searching,
 but the content of array are being sorted in length
 or letter order for show that the target is too big
 or small(out of range), if that out of range ,the
 searching will stop.

 here is the sample:
 sample 2:
var
 name:array [1..5] of string;
 k:integer;
 target:string;
begin
  name[1]:=sam;     {sorting are required,in this way,
                              the name are sorted in length}
  name[2]:=John;
  name[3]:=mark;
  name[4]:=susan;
  name[5]:=simpson;
 
  write('enter target name here:');
  readln(target);

 {linear ordered searching}
  k:=0;
  repeat
   k:=k+1;
  until (target=name[K]) or (target>name[5]);
  {target>name[5] checking are required}

  if name[K]=target then
   writeln('target ',name[K],' find in array',K)
  else
   writeln('target not found');
 end.
 

here come a hardest and most useful one:
binary search:
this searching require more shorter time when
there are a lot of data in array,like 100000000.
note:I will not have no response if you tell me
the first element is the target!!  :-)
warning :sorting of element are required.

the structure of this search is hard to tell you,
but we can see this searching sample to prove that:
 

first ,we have 10 element:
1.Kim wong
2.Philip Au
3.Bill gates
4,Bruce Lee.-           upper part of element /\
5.Felix Chan -          mid element
6.Wilson Luk-          lower part of element  \/
7.Eric Yeung
8.Jackie Chan
9.Peter Yeung
10.Robson Fung
and,our target is Bill gates,

By using Binary search,
the computer will first detect the mid element "5.Felix Chan"
about that word length.then,Bill gates is shorter then Felix Chan
so ,the lower part of  element and mid element will be cutted become:
1.Kim wong -    upper part of element /\
2.Philip Au  -    mid element
3.Bill gates -   lower part of element  \/
4,Bruce Lee.
 

afterward,the computer will check about the mid element "Philip Au"
"Bill gates" is smaller than "Philip Au",so the upper and mid element will be cutted
 become:
1.Bill gates -  mid element
2,Bruce Lee.

then ,"bill gates"  found.

let's see a sample program about that:
sample 3:
var
 name:array [10] of string;
 Index,
 Top,Bottom,Middle:integer;
 target:string;
 found:boolean;
begin
  name[1]:='Kim wong';
  name[2]:='Philip Au';
  :
  :
  {until name[10] defined}

  writeln('enter target here:');
  readln(target);

  Top:=1;
  Bottom:=max;
  Found :=false;
  repeat
    middle:=(top+Bottom) div 2;
    if  target < Name[Middle] then
      Bottom:=Middle-1
    else if target > name[Middle] then
      Top Middle+1
    else
      begin
        Found :=true;
        Index :=Middle
       end;
   until Found or (Top >Bottom)
   if Found=True then
    writeln('target found at :',index)
   else
     writeln('Target not find');
end.

<< Previous || Next >>