Difference between Linear Search and Binary Search in Linked List
Linear search is very slow in huge Linked List records. Instead of this, binary search can be preferred. This method reads only pointer record from disk because there is not enough memory for all records. In this research performance difference between linear search and binary search was examined. It was found that there is a significant speed difference between two methods.
A little Bit about Method
For real random record generation noble prime number 80051 was used. Linked List record file was generated from 1-80051 and randomized. Then addition to linked list method was used to fill the whole records. So never a sequential access could be done to record file. Here file access speeds were tested.
C Source Code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#include<dos.h>
#include<time.h>
#include<sys/timeb.h>
#define file_name "bnsearch.txt"
#define file_name2 "bnsearLi.txt"
#define file_name3 "bnsearLi.dat"
#define Asil_Number 80051
// Suppose there is 80051 records.
typedef struct {
long num, point;
long free[1000];
} LinkL;
int generate_random_list()
{
long i, k, *Asil;
FILE *fl;
fl = fopen(file_name,"w");
Asil = (long *)calloc(Asil_Number+1,sizeof(long));
if (Asil==NULL)
{
printf("There is not enough memory.");
return(-1);
}
k = Asil_Number >> 1;
for(i=1;i<Asil_Number+1;i++)
{
k = k % Asil_Number;
Asil[i] = k;
k = k*10;
}
Asil[Asil_Number] = Asil_Number; // here last element is writing to last place
for(i=0;i<Asil_Number+1;i++)
fprintf(fl,"%ld\n",Asil[i]);
free(Asil);
fclose(fl);
return 0;
}
int generate_linked_list_file()
{
long i, k,x,j, *A, *PO;
FILE *fl1, *fl2;
LinkL LList;
clock_t t_begin, t_end;
fl1 = fopen(file_name,"r");
fl2 = fopen(file_name3,"wb");
A = (long *)calloc(Asil_Number+1,sizeof(long));
if (A==NULL)
{
printf("A : There is not enough memory.");
return 0;
}
PO = (long *)calloc(Asil_Number+1,sizeof(long));
if (PO==NULL)
{
printf("PO : There is not enough memory.");
free(A);
return 0;
}
i = 0;
while(!feof(fl1))
{
fscanf(fl1,"%ld\n",&A[i]);
i++;
}
t_begin = clock();
PO[0] = 1;
PO[1] = -1;
for(i=2;i<Asil_Number+1;i++)
{
x = A[i];
j = PO[0];
k = 0;
while((j>0) && (x>A[j]))
{
k = j;
j = PO[j];
}
PO[k] = i;
PO[i] = j;
}
t_end = clock();
printf("Elapsed time : %4.6f", (double)(t_end - t_begin) / CLOCKS_PER_SEC);
for(i=0;i<Asil_Number+1;i++)
{
LList.num = A[i];
LList.point = PO[i];
fwrite(&LList, sizeof(LinkL), 1, fl2);
}
free(A);
free(PO);
fclose(fl1);
fclose(fl2);
return 0;
}
int binary_search()
{
long i, j, k, n, tmp, x, *PO,look_count;
FILE *fl;
LinkL LLink;
struct _timeb t_begin, t_end;
char ch=0;
fl = fopen(file_name3,"rb");
PO = (long *)calloc(Asil_Number+10,sizeof(long));
if (PO==NULL)
{
printf("PO : There is not enough memory.");
return -1;
}
i = 0;
while(!feof(fl))
{
fread(&LLink, sizeof(LinkL), 1, fl);
PO[i] = LLink.point;
i++;
}
while (ch != 27)
{
printf("Enter the record ID to be searched:"); scanf("%d",&x);
_ftime(&t_begin);
j=PO[0];
n = Asil_Number;
fseek(fl, j*sizeof(LinkL), SEEK_SET);
fread(&LLink, sizeof(LinkL), 1, fl);
look_count = 1;
while ( (n > 1) && (x != LLink.num) && (j > 0))
{
n = (n+1) / 2;
tmp = j;
i = 0;
while ( (i < n) && (j>0) )
{
k = j;
j = PO[j];
i++;
}
if (j > 0)
{
fseek(fl, j*sizeof(LinkL), SEEK_SET);
printf("Position in file:%ld\n", ftell(fl));
if( fread(&LLink, sizeof(LinkL), 1, fl) != 1)
{
printf("%s : Couldn't be read.\nPosition: %ld \n",
file_name3, ftell(fl));
fclose(fl);
return (-1);
}
look_count++;
if ( x < LLink.num )
j = tmp;
}
}
if ( (x == LLink.num) && (j != 0))
{
printf("Number ID %ld īs place in array is %ld\n", x, j);
printf("Number ID %ld found in %ld search attempts\n",x, look_count);
}
else if (j < 0)
// k is the last rocord's pointer and it gives the current record number.
{
printf("Number ID %ld īs place in array is %ld\n", x, j);
printf("Number ID %ld found in %ld search attempts\n",x, look_count);
}
else
printf("Number ID %ld is not in array A.\n",x);
_ftime(&t_end);
printf("Elapsed time : %ld ms\n", t_end.millitm - t_begin.millitm);
printf("\nWill you search for a new record(ESC exit)?\n");
ch = getch();
}
free(PO);
fclose(fl);
return 0;
}
int lineer_search()
{
long i, j, k, n, x, *PO,look_count;
FILE *fl;
LinkL LLink;
clock_t t_begin, t_end;
char ch=0, tmpbuf[128], tmpbuf2[128];
fl = fopen(file_name3,"rb");
PO = (long *)calloc(Asil_Number+10,sizeof(long));
if (PO==NULL)
{
printf("PO : There is not enough memory.");
return -1;
}
i = 0;
while(!feof(fl))
{
fread(&LLink, sizeof(LinkL), 1, fl);
PO[i] = LLink.point;
i++;
}
while (ch != 27)
{
printf("Enter the record ID to be searched :"); scanf("%d",&x);
t_begin = clock();
_strtime( tmpbuf );
j=PO[0];
n = Asil_Number;
fseek(fl, j*sizeof(LinkL), SEEK_SET);
fread(&LLink, sizeof(LinkL), 1, fl);
look_count = 1;
k = j;
while ( (x > LLink.num) && (j > 0))
{
k = j;
j = PO[j];
fseek(fl, j*sizeof(LinkL), SEEK_SET);
if( fread(&LLink, sizeof(LinkL), 1, fl) != 1)
{
printf("%s : Couldn't be read.\nPosition: %ld \n", file_name3, ftell(fl));
fclose(fl);
return (-1);
}
look_count++;
}
if ( (x == LLink.num) && (j > 0))
{
printf("Number ID %ld īs place in array is %ld\n", x, j);
printf("Number ID %ld found in %ld search attempts\n",x, look_count);
}
else
printf("Number ID %ld is not in aray A.\n",x);
t_end = clock();
_strtime( tmpbuf2 );
printf("Elapsed time : %4.4f s", (double)(t_end - t_begin) / CLOCKS_PER_SEC);
printf("\nTime difference: %s %s", tmpbuf, tmpbuf2);
printf("\n Will you search for a new record(ESC exit)?\n");
ch = getch();
}
free(PO);
fclose(fl);
return 0;
}
void main()
{
generate_random_list();
generate_linked_list_file();
binary_search();
lineer_search();
}
Sample Execution
Binary Search
Enter the record ID to be searched :2000
Number ID 2000 īs place in array is 74471
Number ID 2000 found in 16 search attempts
Elapsed Time : 40 ms
Lineer Search
Enter the record ID to be searched :2000
Number ID 2000 īs place in array is 74471
Number ID 2000 found in 2000 search attempts
Elapsed Time : 4.9870 s
Time difference: 01:10:52 01:10:57
Result
Harddisk Features
Average Seek Time : 7 ms
Random Read : 6 MB/s
Sequential Read : 25 MB/s
Buffered Read : 48 MB/s
File Size : 305 MB = 320.848.416 byte
Used Noble Prime Number: 80051
Number of Records : 80051
One Record Size : 4008 Byte
|
Record No |
Binary Search (min:sec:ms) |
Linear Search (min:sec:ms) |
|
10 |
00:00:40 |
00:00:200 |
|
1000 |
00:00:40 |
00:02:374 |
|
2000 |
00:00:40 |
00:04:987 |
|
4000 |
00:00:60 |
00:10:425 |
|
8000 |
00:00:90 |
00:21:761 |
|
16000 |
00:00:70 |
00:48:981 |
|
32000 |
00:00:40 |
02:03:888 |
|
44000 |
00:00:70 |
03:11:445 |
|
60000 |
00:00:70 |
04:50:919 |
|
80051 |
00:00:40 |
06:47:707 |
For accessing last record difference between Linear Search and Binary Search is 1/10000.