جستجو در آرایه در پاسکال :
در اغلب موارد به جستجوی یک مقدار در آرایه نیاز خواهید داشت
برای مثال فرض کنید نمرات درس پاسکال مربوط به 10 دانش آموز را به وسیله یک آرایه 10 عنصری از ورودی دریافت کرده اید
وحال میخواهید وجود یا عدم وجود نمره خاصی ( مثل 20 ) را در میان نمرات برسی نمایید
برای این منظور باید عمل جستجو را در آرایه انجام دهید
برای جستجو روشهای متعددی وجود دارد که هر یک مزایاو معایبی دارند و در مواقع خاصی کاربرد خواهند داشت
یکی از روشهای معمول روش جستجوی دودویی است که به آن Binary Search گفته میشود
در روش جستجوی دودویی باید آرایه مرتبشده باشد
در این روش در هر بار جستجو نیمی از آرایه در نظر گرفته میشود
برای مثال اگر آرایه شامل 10 عنصر باشد ابتدا عنصر مورد جستجو با عنصر وسطی آرایه ( یعنی عنصر پنجم ) مقایسه میگردد
درصورتی که جستجو موفقیت آمیز باشد
عمل جستجو خاتمه می یابد در غیر این صورت اگر عنصر مورد جستجو وسطی آرایه ( یعنی عنصر پنجم ) کوچک تر باشد
به این معناست که جستجو باید روی نیمه اول آرایه ( یعنی 5 عنصر اول ) آن صورت بگیرد
و اگر عنصر مورد جستجو از عنصر وسطی آرایه ( یعنی عنصر پنجم ) بزرگتر باشد
این معناست که جستجو باید روی نیمه دوم آرایه ( یعنی 5 عنصر دوم ) آن صورت بگیرد
این عملیات تا زمانی تکرار میشود که عمل جستجو با موفقیت یا عدم موفقیت خاتمه بیابد
برای مثال فرض کنید آرایه 10 عنصری مرتب شده زیر در اختیار باشد
| 30 | 20 | 15 | 12 | 10 | 8 | 6 | 5 | 4 | 2 |
برای یافتن عدد 10 با استفاده از روش جستجوی دودویی به صورت زیر عمل میشو
1 – ابتدا عدد 10 با عنصر وسطی آرایه ( یعنی عدد 8 ) مقایسه می گردد
با توجه به اینکه عدد 10 از 8 بزرگ تر است لذا نیمه دوم آرایه مورد جستجو قرار می گیرد
نیمه دوم
| 30 | 20 | 15 | 12 | 10 |
2- عدد 10 با عنصر وسطی ارایه ( یعنی عدد 15 ) مقایسه می گردد
با توجه به اینکه عدد 10 از 15 کوچک تر است لذا نیمه اول آرایه مورد جستجو قرار می گیرد
نیمه اول آرایه
| 12 | 10 |
3 – عدد 10 با عنصر وسطی آرایه ( یعنی عدد 10 ) مقایسه میگردد
با توجه به اینکه هر دو مقدار مساوی هستند لذا عمل جستجو با موفقیت خاتمه می یابد
| نکتــــــــــــــه |
|---|
| درروش جستجوی دودویی برای یافتن عنصر وسطی آرایه از روش زیر استفاده میشود |
در برنامه زیر از روش جستجوی دودویی برای جستجو در آرایه استفاده شده است
uses Crt;
{ Type Declarations }
type
elementist = [1..10] of byte;
const
Size=10;
a:elementiist = (1.2.3.4.5.6.7.8.9.10);
{variable Declarations}
var
q,w:integer;
{====== <<compare>> ======}
function compare (x,y:byte): char;
begin
if x>y then
compare := '>'
else if x<y then
compare :='<'
else
compare:='=';
end;
{======<<BINARY_SEARCH>>======}
procdure binary_search(a:elementiist;x:byte; var n,j:integer);
{variable Declarations}
var
left.right,middle:integer;
found:boolean;
begin
left:1; right:=n; fond:=false; j:=0;
while (left<=right) and (not found) do
begin
middle:=(left+right) div 2;
case compare(x,a[middle]) of
:left:=middle+1;'>'
:right:=middle-1;'<'
'=':begin
j:=middle;
found:=true;
end;
end; {case}
end;
end.
begin
clrscr;
q:size;
writeLn('Please Enter a Number : ');
readln(w);
binary_search(a,w,q,w);
if w<> 0 then
witeln (' index = ',w)
else
write ('The Number Not Found');
readkey
end. {main}
