Outta_Breathe1020
28th December 2012, 07:25 AM
الگوریتم های جستجو
زبان C
موارد زيادي پيش مي آيند که قصد داريم به دنبال يک داده در يک آرايه جستجو کرده و مکان آن را پيدا کنيم. در این تاپیک دو روش متداول جستجو را مورد بررسي قرار مي دهيم. البته معمولا براي عمل جستجو از ساختمان داده هاي پيچيده تري همچون درختهاي جستجوي دودويي استفاده مي گردد.
جستجوی خطی
جستجوي خطي، ساده ترين نوع جستجو است که در آرايه هاي نامرتب استفاده مي شود. در اين روش داده مورد نظر به ترتيب با تک تک عناصر آرايه مقايسه مي شود تا مکان آن پيدا شود. تابع زير پياده سازي اين جستجو را نشان مي دهد: (دريافت برنامه) (http://vu.um.ac.ir/content/158/ch10/linearSearch.cpp)
int linearSearch(int A[], int n, int x) {
int i;
++ for (i=0; i<n; i)
if (x == A[i] ) return(i);
return(-1) ;
}
در تابع فوق، پارامتر A آرايه موردنظر و n اندازه آن را مشخص مي نمايد. پارامتر x نيز داده اي است که بدنبال آن جستجو مي کنيم. همانطور که مي بينيد جستجو را از اولين خانه آرايه شروع کرده و چنانچه x با هريک از عناصر آرايه برابر بود، بلافاصله مکان آن را باز مي گردانيم. در پايان چنانچه داده موردنظر پيدا نشد، مقدار -1 را باز مي گردانيم.
اگر آرايه داراي n عنصر باشد، در بدترين حالت نياز به n مقايسه براي پيدا کردن داده مورد نظر داريم و اين در صورتي است که داده در آخرين مکان آرايه قرار داشته باشد. اما از آنجا که احتمال قرار گرفتن داده در هريک از مکانهاي آرايه يکسان است، بطور متوسط نياز به n/2 مقايسه خواهيم داشت. اين تعداد مقايسه براي آرايه هاي بزرگ، زمان زيادي را صرف خواهد کرد. بطور کلي اين روش فقط براي آرايه هاي کوچک مناسب است.
جستجوی دودویی
چنانچه آرايه مورد جستجو مرتب شده باشد، روش بسيار کاراتري براي جستجو وجود دارد. اين روش که به جستجوي دودويي موسوم است، با هربار مقايسه، نيمي از عناصر آرايه را از بازه جستجو حذف مي نمايد. در نتيجه جستجو در يک آرايه بزرگ با سرعت بسيار زيادي صورت مي پذيرد.
براي تشريح الگوريتم، فرض کنيد آرايه موردنظر بصورت صعودي مرتب شده است. ابتدا عنصر وسط آرايه را پيدا کرده و داده مورد جستجو را با آن مقايسه مي کنيم. سه حالت ممکن است رخ دهد:
اگر داده مورد جستجو با عنصر وسط آرايه مساوي باشد، داده پيدا شده و مکان آن را باز مي گردانيم.
اگر داده مورد جستجو از عنصر وسط آرايه کوچکتر باشد، بنابراين بايد در نيمه اول آرايه به دنبال آن جستجو نماييم.
اگر داده مورد جستجو از عنصر وسط آرايه بزرگتر باشد، بنابراين بايد در نيمه دوم آرايه به دنبال آن جستجو نماييم.
چنانچه حالت اول رخ دهد، جستجو پايان يافته و مکان داده بازگردانده مي شود.
اما اگر حالت دوم يا سوم رخ دهد، عمليات جستجو به روش فوق مجددا براي نيمه اول يا نيمه دوم آرايه تکرار مي شود. بدين ترتيب بازه مورد جستجو به نيمي از آرايه کاهش مي يابد. با تکرار اين عمليات هربار بازه مورد جستجو نصف مي شود. عمليات تا زماني ادامه مي يابد که يا داده مورد نظر پيدا شود و يا بازه مورد جستجو آنقدر کوچک شود که داده اي باقي نماند (يعني طول بازه مورد جستجو به صفر برسد)، که در اينصورت داده در آرايه وجود ندارد.
به نحوه پياده سازي اين الگوريتم توجه نماييد: (دريافت برنامه) (http://vu.um.ac.ir/content/158/ch10/binarySearch.cpp)
int binarySearch(int A[], int n, int x) {
int low, high, mid;
low = 0;
high = n-1;
while (low <= high) {
mid = (low + high) / 2;
if (x == A[mid]) return(mid);
else if (x < A[mid]) high = mid-1;
else low = mid + 1;
}
return(-1);
}
در تابع فوق، پارامتر A آرايه موردنظر و n اندازه آن را مشخص مي نمايد. پارامتر x نيز داده اي است که بدنبال آن جستجو مي کنيم.متغيرهاي محلي low و high به ترتيب حد بالا و حد پايين بازه مورد جستجو را نشان مي دهند.
متغير mid نيز براي محاسبه مکان وسط بازه جستجو بکار مي رود. در ابتدا بازه جستجو برابر کل آرايه است، لذا low برابر 0 و high برابر n-1 قرار دارد. در هر مرحله (هر بار اجراي حلقه)، بسته به نتيجه مقايسه عنصر مورد جستجو (x) و عنصر وسط بازه جستجو (A[mid])، مقدار low يا high بروزرساني مي شود که باعث مي شود بازه جستجو نصف شود. چنانچه low از high بزرگتر شود، طول بازه جستجو به صفر رسيده است و در نتيجه حلقه خاتمه يافته و مقدار -1 به معناي پيدا نشدن داده بازگردانده مي شود.
1020
زبان C
موارد زيادي پيش مي آيند که قصد داريم به دنبال يک داده در يک آرايه جستجو کرده و مکان آن را پيدا کنيم. در این تاپیک دو روش متداول جستجو را مورد بررسي قرار مي دهيم. البته معمولا براي عمل جستجو از ساختمان داده هاي پيچيده تري همچون درختهاي جستجوي دودويي استفاده مي گردد.
جستجوی خطی
جستجوي خطي، ساده ترين نوع جستجو است که در آرايه هاي نامرتب استفاده مي شود. در اين روش داده مورد نظر به ترتيب با تک تک عناصر آرايه مقايسه مي شود تا مکان آن پيدا شود. تابع زير پياده سازي اين جستجو را نشان مي دهد: (دريافت برنامه) (http://vu.um.ac.ir/content/158/ch10/linearSearch.cpp)
int linearSearch(int A[], int n, int x) {
int i;
++ for (i=0; i<n; i)
if (x == A[i] ) return(i);
return(-1) ;
}
در تابع فوق، پارامتر A آرايه موردنظر و n اندازه آن را مشخص مي نمايد. پارامتر x نيز داده اي است که بدنبال آن جستجو مي کنيم. همانطور که مي بينيد جستجو را از اولين خانه آرايه شروع کرده و چنانچه x با هريک از عناصر آرايه برابر بود، بلافاصله مکان آن را باز مي گردانيم. در پايان چنانچه داده موردنظر پيدا نشد، مقدار -1 را باز مي گردانيم.
اگر آرايه داراي n عنصر باشد، در بدترين حالت نياز به n مقايسه براي پيدا کردن داده مورد نظر داريم و اين در صورتي است که داده در آخرين مکان آرايه قرار داشته باشد. اما از آنجا که احتمال قرار گرفتن داده در هريک از مکانهاي آرايه يکسان است، بطور متوسط نياز به n/2 مقايسه خواهيم داشت. اين تعداد مقايسه براي آرايه هاي بزرگ، زمان زيادي را صرف خواهد کرد. بطور کلي اين روش فقط براي آرايه هاي کوچک مناسب است.
جستجوی دودویی
چنانچه آرايه مورد جستجو مرتب شده باشد، روش بسيار کاراتري براي جستجو وجود دارد. اين روش که به جستجوي دودويي موسوم است، با هربار مقايسه، نيمي از عناصر آرايه را از بازه جستجو حذف مي نمايد. در نتيجه جستجو در يک آرايه بزرگ با سرعت بسيار زيادي صورت مي پذيرد.
براي تشريح الگوريتم، فرض کنيد آرايه موردنظر بصورت صعودي مرتب شده است. ابتدا عنصر وسط آرايه را پيدا کرده و داده مورد جستجو را با آن مقايسه مي کنيم. سه حالت ممکن است رخ دهد:
اگر داده مورد جستجو با عنصر وسط آرايه مساوي باشد، داده پيدا شده و مکان آن را باز مي گردانيم.
اگر داده مورد جستجو از عنصر وسط آرايه کوچکتر باشد، بنابراين بايد در نيمه اول آرايه به دنبال آن جستجو نماييم.
اگر داده مورد جستجو از عنصر وسط آرايه بزرگتر باشد، بنابراين بايد در نيمه دوم آرايه به دنبال آن جستجو نماييم.
چنانچه حالت اول رخ دهد، جستجو پايان يافته و مکان داده بازگردانده مي شود.
اما اگر حالت دوم يا سوم رخ دهد، عمليات جستجو به روش فوق مجددا براي نيمه اول يا نيمه دوم آرايه تکرار مي شود. بدين ترتيب بازه مورد جستجو به نيمي از آرايه کاهش مي يابد. با تکرار اين عمليات هربار بازه مورد جستجو نصف مي شود. عمليات تا زماني ادامه مي يابد که يا داده مورد نظر پيدا شود و يا بازه مورد جستجو آنقدر کوچک شود که داده اي باقي نماند (يعني طول بازه مورد جستجو به صفر برسد)، که در اينصورت داده در آرايه وجود ندارد.
به نحوه پياده سازي اين الگوريتم توجه نماييد: (دريافت برنامه) (http://vu.um.ac.ir/content/158/ch10/binarySearch.cpp)
int binarySearch(int A[], int n, int x) {
int low, high, mid;
low = 0;
high = n-1;
while (low <= high) {
mid = (low + high) / 2;
if (x == A[mid]) return(mid);
else if (x < A[mid]) high = mid-1;
else low = mid + 1;
}
return(-1);
}
در تابع فوق، پارامتر A آرايه موردنظر و n اندازه آن را مشخص مي نمايد. پارامتر x نيز داده اي است که بدنبال آن جستجو مي کنيم.متغيرهاي محلي low و high به ترتيب حد بالا و حد پايين بازه مورد جستجو را نشان مي دهند.
متغير mid نيز براي محاسبه مکان وسط بازه جستجو بکار مي رود. در ابتدا بازه جستجو برابر کل آرايه است، لذا low برابر 0 و high برابر n-1 قرار دارد. در هر مرحله (هر بار اجراي حلقه)، بسته به نتيجه مقايسه عنصر مورد جستجو (x) و عنصر وسط بازه جستجو (A[mid])، مقدار low يا high بروزرساني مي شود که باعث مي شود بازه جستجو نصف شود. چنانچه low از high بزرگتر شود، طول بازه جستجو به صفر رسيده است و در نتيجه حلقه خاتمه يافته و مقدار -1 به معناي پيدا نشدن داده بازگردانده مي شود.
1020