Searching Techniques

 Developed by Hardeep Singh Copyright © Hardeep Singh, 2000-2009 EMail seeingwithc@hotmail.com Website seeingwithc.org All rights reserved. The code may not be used commercially without permission. The code does not come with any warranties, explicit or implied. The code cannot be distributed without this header.

Problem: Given a list of distinct numbers (LIST), and another number (A), find the index of A in LIST if it is present or indicate that it is not present.

Although we have narrated the problem for numbers, it can actually refer to any datatype that can be compared for equality and arranged in order, such as strings.

Note: In the text below, lg(n) means log of n to base 2.

Solution #1: The naive approach

The simplest way, of course, is to compare the given number to each of the numbers in the list. If a number in the list matches the given number A, we can return the index of that number. If we reach the end of the list, we can indicate that A does not exist in LIST. Here is an implementation of this simple algorithm:

```#include <stdio.h>

#define MAXELT 50

int main()
{
int i=-1,n=0,list[MAXELT],a;
char t;
int linear_search(int list[],int n,int a);

if (i!=-1)
list[i++]=n;
else
i++;
printf("\nEnter the numbers <End by #>");
fgets(t,sizeof t,stdin);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);

printf("\nEnter the number to be searched for >");
scanf("%d",&a);

int pos=linear_search(list,i,a);        //do linear search

if (pos==-1)                            //print the result
printf("\nThe number does not exist in the list.\n");
else
printf("\nThe number exists at location %d.\n",pos+1);
return(0);
}

int linear_search(int list[],int n,int a)
{
int i;
for (i=0;i<n;i++)                       //step through the list
if (list[i]==a)                 //if found, return
return i;
}

//Note that we did not even need to store the numbers in a list in this
//case. We could have kept comparing as we received. However, if multiple
//searches are to be done on a single list, this is not possible. In this
//case, we used this method to ensure conformity with other methods to be
//shown next.

```

Since this algorithm compares the given number to all N elements of the list, it is an O(n) algorithm. Due to this reason, this algorithm is known as Linear Search.

Better search algorithms do exist and we will come to that, however this one is quite flexible: it doesn't require any restriction on the order in which numbers appear in the input list. So it can be used even if the list is not sorted or if the medium on which the list is stored requires sequential access (eg. Tapes).

Solution #2: Binary Search

This algorithm goes as follows (it requires a sorted list in input, unlike the previous algorithm):

1. Find the middle element of the list.
2. Compare the middle element with A (the given element).
3. If both are equal, return the index of the middle element.
4. If they are not equal, then
1. if A is smaller than the middle element, then we must search for A in the upper half of the list (remember: the list is sorted)
2. otherwise, we must search in the lower half.
5. Now in the smaller list, find the middle element and repeat the process. An implementation of the algorithm is given below:

(Here, we show only the changed function binary_search. The rest of the program is the same as in linear search, just change linear_search function with binary_search and change all references to linear_search.)

```int binary_search(int list[],int n,int a)
{
int first=0,last=n-1,mid;

while (first<=last) {                   //iterate while first<=last
mid=(first+last)/2;             //calculate mid=trunc((f+l)/2)
if (list[mid]==a)               //found
return mid;
last=mid-1;             //upper half of list
else
first=mid+1;            //look in lower half
}
}
```

Some people also implement binary search in the following recursive way:

```int binary_search_dash(int list[],int first,int last,int a)
{
int mid;

if (first<=last) {
mid=(first+last)/2;
if (list[mid]==a)
return mid;
else if (a<list[mid])
return binary_search_dash(list,first,mid-1,a);
else
return binary_search_dash(list,mid+1,last,a);
}
return -1;
}
```

Although this is a more direct implementation of the above description, it uses more stack space compared to the first implementation, and is much slower on most systems. Also, this form of recursion is called 'Tail Recursion', which is the worst form of recursion. Recursion is a powerful tool which must be used with care. Recursion is advised only in certain cases, where it does not impose unnecessary action, as in Quicksort.

Binary search is O(lg(n)) as it halves the list size in each step. It is a large improvement over linear search; for a list with 10 million entries, while linear search will need 10 million key comparisons, binary search will need just about 24. Although binary search is already very good, at times it can be slightly improved, lets see how.

Solution #3: Fibonacci Search

Who does not know about Fibonacci numbers? They crop up in so many diverse problems that can't even be listed! From estimation of the number of rabbits in successive generations, to the number of leaves on branches, fibonacci numbers have far-reaching uses. In future Seeing With C might feature a write-up on different ways of generating them, here we will see ways of using them! (Generation of Fibonacci numbers is another misuse of recursion.)

The fibonacci series has 1 as the first two terms and each successive term is the sum of two previous terms. So, it goes 1,1,2,3,5,8,13,21,44,...etc. Each number appearing in the fibonacci series is called fibonacci number.

Fibonacci search changes the binary search algorithm slightly: instead of halving the index for a search, a fibonacci number is subtracted from it. The fibonacci number to be subtracted decreases as the size of the list decreases.

Have a look at its implementation:

```int fibonacci_search(int list[],int n,int a)
{
int f1,f2,mid,first,index;

f1=1; f2=0; mid=2;                      //initialise the first two fibonacci
//numbers. F1 will be the main
while (f1<n) {                          //set F1 to a number >= n
f1=f1+f2;
f2=f1-f2;
mid++;
}
f2=f1-f2;                               //set F1 to the largest number <=n
f1=f1-f2;
mid--;
first=0;

while (mid>0) {                         //loop
index=first+f1;
printf("\nfirst:%d,index:%d,f1:%d,list:%d,mid:%d,a:%d",first,index,f1,list[index],mid,a);
if (index>=n || a<list[index]) {
mid--;                    //if the number is bigger, move back
f2=f1-f2;                 //to a smaller fibonacci number
f1=f1-f2;
}
else if (a==list[index])         //found: return the index
return(index);
else {
first=index;              //if the number is smaller, move to the
mid=mid-2;                //second part of the list and
f1=f1-f2;                 //reduce F1 back two F-numbers
f2=f2-f1;
}
}

}
```

Whew, this one has the longest code so far. It is also O(lgn) algorithm.

In order to compare the three algorithms shows, we did a small test, on six lists with sizes varying from 15 to 1000. On the same list, we performed four searches each - a mix of existing and non existing numbers. The first list was not sorted - hence the result from binary and fibonacci searches were expected to be wrong. The number of comparisons carried out by each algorithm was tracked.
The following graphs show the comparison - the first one the left shows the result from a single individual search, and the second cumulative from all searches:  Its obvious that Binary search is the best of all (for sorted data, of course) - however the margin with Fibonacci search isn't huge.
So what is Fibonacci search useful for? One of the key advantages with Fibonacci search over Binary search is that comparison dispersion is low, so for example if Binary and Fibonacci searches just compared element 100, and Binary search now compares element 200, Fibonacci search will now compare element 150. This means that for mediums that are accessed sequentially, especially tape drives, Fibonacci search makes more sense.

In this part, I will express the linear and the binary search algorithms in 80386 assembly language. This, is towards the following goals:

1. For people who don't understand assembly/machine languages, its instructive to get some idea of what happens during the compilation of the code that they write. Especially notice the fact that what look like two distinct key comparisons in the main loop of binary search can be achieved with just one CoMPare instruction at the assembly level, therefore it is always counted as one.
2. For those who know a little assembly but work mainly in C/C++, this is one more example to work through.
3. For those who already know assembly, I want to provide them with ready made timesaver routines. Even while writing C/C++ software, these assembly routines can be used to speed things up, since all C/C++ compilers allow facilities to write inline assembly code.

Linear Search

Precondition: CX holds the number of entries, SI has been initialised to first array element, D=0.

```AGAIN: LODSD            ; The instruction reads the next number from memory
; into a CPU register(EAX)
CMP EAX,EBX      ; Compare registers EAX and EBX. EBX already holds
; the value to be found
LOOPNE AGAIN     ; Loop if EAX and EBX Not Equal and all entries have
; not been exhausted - to statement labeled AGAIN
CMP EAX,EBX      ; Out of the loop - Two things are possible: EAX and
; EBX were found equal, or all list entries exhausted
; So, compare to make sure
JNE LABEL1       ; Jump if Not Equal to LABEL1
...              ; Code to announce the fact that the entry has been
; found at location marked by CX and exit
LABEL1:...              ; Code to announce that the number has not been
; found and exit.
```

Binary Search

```AGAIN: MOV AL,FIRST     ; Register AL <- Memory location containing FIRST
CMP AL,LAST      ; CoMPare AL (FIRST) with LAST
JA NOTFOUND      ; Jump if Above - to NOTFOUND since FIRST>LAST
SHR AL,1         ; SHift Right AL once, this will divide it by 2
MOV MID,AL       ; Send current value of AL to memory location MID
MOVZX AX,AL      ; AX <- AL. (This is called MOV Zero eXpanded)
SHL AX,2         ; SH Left AX by 2. This multiplies it by 4. This is
done because each array value is of \$ bytes.
; Now AX contains the address of MID element
MOV SI,AX        ; SI <- AX
LODSD            ; Read value from memory location SI into EAX
CMP EAX,N        ; CoMPare EAX with N, the number to be found
JE FOUND         ; Jump if Equal to FOUND
JL LESS          ; Jump if Less to LESS (to lower list). Note that
; no comparison is done here, just a jump. Just one
; comparison was done in CMP statement above. The flags
; hold the result which is checked by the jump
; instruction. Jump is equivalent to a simple goto
; in high level language; it does not do any inherent
; comparison
MOV AL,MID       ; AL <- MID
DEC AL           ; AL <- AL-1
MOV LAST,AL      ; LAST <- AL. These three instructions accomplish
; LAST=MID-1.
JMP AGAIN        ; Iterate
LESS:  MOV AL,MID       ; AL <- MID
INC AL           ; AL <- AL+1
MOV FIRST,AL     ; FIRST <- AL. These three instructions accomplish
; FIRST=MID+1
JMP AGAIN        ; JuMP

FOUND: ...              ; Code to indicate "Found number" at location contained
by SI and exit 