|
Linked List: Binary Search |
|
|
|
While handling huge amount of data, searching sequentially comes impossible. So another way of search is needed; that is binary search. At first place only pointers are buffered. Then the pointers are used as source of search.
The Algorithm 
Pascal Source Code
uses crt;
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.
|
Studies