Linear search
One way to know how many element are in the array is to pass the length as an argument; another is to place a NULL marker at the end of the array:
// lookup: sequential search for word in array
int lookup(char *word, char *array[])
{
int i;
for(i=0; array[i] != NULL;i++)
if(strcmp(word, array[i])==0)
return i;
return -1;
}
Binary search
For binary search, the table must be sorted,and we must know how long the table is .The NELEMS macro we wrote before can help.
Here is an excerpt.
printf("the HTML table has %d words\n", NELEMS(htmlchars));
// Binary search for name in tab; return index
int lookup(char *name, Nameval tab[], int ntab)
{
int low,high,mid,cmp;
low=0;
high=ntab-1;
while(low <=high){
mid=(low+high)/2;
cmp=strcmp(name,tab[mid].name);
if(cmp<0)
high=mid-1;
else if (cmp >0)
low=mid+1;
else
return mid; //found match
}
return -1; //no match;
}
Binary search is faster than linear search especially when you have a large size of input. Ignoring roundoff, the proportion is log2n.
