Binary Search in Linked List
Sequential search comes impossible, when there is huge amount of data. So there is another way of search: binary search. Firstly pointer record is taken into buffer array. When search is needed this pointer is used.
The Algorithm
Pascal Source Code
var
i,j,k,tmp,n,x:integer;
A:array[1..14] of integer;
PO:array[0..14] of integer;
BEGIN
clrscr;
{ Example array and it's pointer array }
A[1]:=20; A[2]:=15; A[3]:=30; A[4]:=40; A[5]:=5;
A[6]:=8; A[7]:=2; A[8]:=7; A[9]:=12; A[10]:=50;
A[11]:=35; A[12]:=100; A[13]:=60; A[14]:=45;
PO[0]:=7; PO[1]:=3; PO[2]:=1; PO[3]:=11; PO[4]:=14;
PO[5]:=8; PO[6]:=9; PO[7]:=5; PO[8]:=6; PO[9]:=2;
PO[10]:=13; PO[11]:=4; PO[12]:=-1; PO[13]:=12; PO[14]:=10;
n := 14;
write('Input the number to be searched:'); readln(x);
j:=PO[0];
while (n > 1) and (x <> A[j]) do
begin
n := (n+1) div 2;
tmp := j;
for i:=1 to n do
begin
k := j;
j := PO[j];
end;
if (x<a[j]) then j := tmp;
end;
if ((x=a[j]) and (j<>0)) then
writeln('Number ',x,' is in ',j,'. place')
else
writeln(x,' is not in array A');
readln;
END.
Sample Execution
Sample Array and its Pointers.
No A[] PO[]
|
0 |
|
7 |
|
1 |
20 |
3 |
|
2 |
15 |
1 |
|
3 |
30 |
11 |
|
4 |
40 |
14 |
|
5 |
5 |
8 |
|
6 |
8 |
9 |
|
7 |
2 |
5 |
|
8 |
7 |
6 |
|
9 |
12 |
2 |
|
10 |
50 |
13 |
|
11 |
35 |
4 |
|
12 |
100 |
-1 |
|
13 |
60 |
12 |
|
14 |
45 |
10 |
Input the number to be searched:100
Number 100 is in 12. place.
Input the number to be searched :35
Number 35 is in 11. place.
Input the number to be searched :30
Number 30 is in 3. place.
Input the number to be searched :2
Number 2 is in 7. place.