Searching Techniques
--------------------
Developed by Hardeep Singh.
Copyright: Hardeep Singh, 2001-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
#define MAXELT 50
int main()
{
int i=-1,n=0,list[MAXELT],a;
char t[10];
int linear_search(int list[],int n,int a);
do { //read the list
if (i!=-1)
list[i++]=n;
else
i++;
printf("\nEnter the numbers ");
fgets(t,sizeof t,stdin);
if (sscanf(t,"%d",&n)<1)
break;
} while (1);
printf("\nEnter the number to be searched for >");
//read the number
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
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 || aLAST
ADD AL,LAST ; ADD LAST to AL. Al now contains 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.
ADD AX,OFFSET ARRAY
; 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
NOTFOUND: ... ; Code to indicate "Not found"
That's all folks!
SeeingWithC.org
http://SeeingWithC.org