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