الگوریتم های جستجو

[Outta_Breathe1020]

الگوریتم های جستجو
زبان C

موارد زيادي پيش مي آيند که قصد داريم به دنبال يک داده در يک آرايه جستجو کرده و مکان آن را پيدا کنيم. در این تاپیک دو روش متداول جستجو را مورد بررسي قرار مي دهيم. البته معمولا براي عمل جستجو از ساختمان داده هاي پيچيده تري همچون درختهاي جستجوي دودويي استفاده مي گردد.

جستجوی خطی

جستجوي خطي، ساده ترين نوع جستجو است که در آرايه هاي نامرتب استفاده مي شود. در اين روش داده مورد نظر به ترتيب با تک تک عناصر آرايه مقايسه مي شود تا مکان آن پيدا شود. تابع زير پياده سازي اين جستجو را نشان مي دهد: (دريافت برنامه)

 
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 مقايسه خواهيم داشت. اين تعداد مقايسه براي آرايه هاي بزرگ، زمان زيادي را صرف خواهد کرد. بطور کلي اين روش فقط براي آرايه هاي کوچک مناسب است.



جستجوی دودویی

چنانچه آرايه مورد جستجو مرتب شده باشد، روش بسيار کاراتري براي جستجو وجود دارد. اين روش که به جستجوي دودويي موسوم است، با هربار مقايسه، نيمي از عناصر آرايه را از بازه جستجو حذف مي نمايد. در نتيجه جستجو در يک آرايه بزرگ با سرعت بسيار زيادي صورت مي پذيرد.

براي تشريح الگوريتم، فرض کنيد آرايه موردنظر بصورت صعودي مرتب شده است. ابتدا عنصر وسط آرايه را پيدا کرده و داده مورد جستجو را با آن مقايسه مي کنيم. سه حالت ممکن است رخ دهد:

• اگر داده مورد جستجو با عنصر وسط آرايه مساوي باشد، داده پيدا شده و مکان آن را باز مي گردانيم.
• اگر داده مورد جستجو از عنصر وسط آرايه کوچکتر باشد، بنابراين بايد در نيمه اول آرايه به دنبال آن جستجو نماييم.
• اگر داده مورد جستجو از عنصر وسط آرايه بزرگتر باشد، بنابراين بايد در نيمه دوم آرايه به دنبال آن جستجو نماييم.

چنانچه حالت اول رخ دهد، جستجو پايان يافته و مکان داده بازگردانده مي شود.
اما اگر حالت دوم يا سوم رخ دهد، عمليات جستجو به روش فوق مجددا براي نيمه اول يا نيمه دوم آرايه تکرار مي شود. بدين ترتيب بازه مورد جستجو به نيمي از آرايه کاهش مي يابد. با تکرار اين عمليات هربار بازه مورد جستجو نصف مي شود. عمليات تا زماني ادامه مي يابد که يا داده مورد نظر پيدا شود و يا بازه مورد جستجو آنقدر کوچک شود که داده اي باقي نماند (يعني طول بازه مورد جستجو به صفر برسد)، که در اينصورت داده در آرايه وجود ندارد.

به نحوه پياده سازي اين الگوريتم توجه نماييد: (دريافت برنامه)

 
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

[Outta_Breathe1020]

براي محاسبه زمان مورد نياز يك جستجو، بايد به اين نكته توجه كرد كه با هر مقايسه، بازه جستجو نصف مي شود. بدترين حالت زماني است كه داده اصلا پيدا نشود و يا در آخرين مقايسه (زماني كه تنها يك عنصر باقي مانده است) پيدا شود. سوال اينجاست كه چند بار مي توان اندازه آرايه را نصف كرد تا سرانجام به يك عنصر رسيد؟ جستجوي يك عنصر در يك آرايه مرتب به روش دودويي حداكثر نياز به مقايسه دارد، كه زمان بسيار مناسبي است. بعنوان مثال در يك آرايه با 1.000.000 عنصر، تنها به 20 مقايسه نياز است. به همين دليل جستجوي دودويي يكي از بهترين روشهاي جستجو محسوب مي گردد.

چنانچه به الگوريتم جستجوي دودويي دقت شود، متوجه مي شويم كه اين الگوريتم داراي خاصيت بازگشتي است. براي حل مسئله اي به طول n، ابتدا يك مقايسه انجام مي دهيم و سپس بسته به نتيجه مقايسه بايد مسئله كوچكتري به طول n/2 را حل نماييم. براي حل مسئله كوچكتر نيز از مجددا همين روش استفاده مي شود. بنابراين مي توان براي جستجوي دودويي، از يك تابع بازگشتي نيز استفاده كرد.(دريافت برنامه)

int  recBinarySearch(int  A[], int low, int high, int x) {
     int mid;
 
     if  (low > high) return(-1);
     mid = (low + high) / 2;
     if  (x == A[mid])  return(mid);
     else  if  (x < A[mid])  return(recBinarySearch(A, low, mid-1, x)) ;
            else return(recBinarySearch(A, mid+1, high, x)) ;
}
 
 

در تابع فوق، پارمتر A‌ آرايه مورد نظر است. اما از آنجا كه در هربار فراخواني تابع recBinarySearch، بازه جستجو تغيير مي كند، حد پايين و بالاي بازه جستجو در قالب پارامترهاي low و high به آن ارسال شده اند. پارامتر x‌ نيز داده مورد جستجو مي باشد. در ابتدا شرط توقف بازگشت بررسي مي گردد. اگر low از high بزرگتر شده باشد، بازه جستجو به صفر عنصر رسيده و در نتيجه داده پيدا نشده است. درغيراينصورت ابتدا وسط بازه جستجو محاسبه شده و داده مورد جستجو با آن مقايسه مي شود. بسته به نتيجه مقايسه، تابع recBinarySearch مجددا با نيمه بالا يا پايين بازه جستجو فراخواني مي گردد. براي اينكار كافي است حد بالا و يا حد پايين جستجو را در فراخواني جديد تغيير دهيم.

نكته مهم در نحوه فراخواني اوليه اين تابع است. مسلما در اولين فراخواني، بازه جستجو برابر كل آرايه است. در نتيجه حد پايين برابر 0 و حد بالا برابر n-1 است كه n اندازه آرايه است. بعنوان مثال چنانچه بدنبال داده 52 در آرايه 100 عنصري data جستجو مي كنيم، بايد تابع را بصورت زير فراخواني نماييم :

recBinarySearch(data, 0, 99, 52)

[rayarasool]

سلام

اگه مجموعه اعداد ما به صورت مرت شده نباشند به غیر از جستجوی خطی دیگه راه دیگه ای هست؟؟

[مدیر تالار برنامه نویسی]

سلام

اگه مجموعه اعداد ما به صورت مرت شده نباشند به غیر از جستجوی خطی دیگه راه دیگه ای هست؟؟

با سلام به دوست عزیزم :»

اگر اعداد مرتب شده باشد که میدونید خودتون بغیر از خطی چه راه حل های دیگه ای وجود دارد
ولی اگر مرتب شده نباشد , مثل این میمونه که شما توی اتاقتون شلوغ پلوغه و هر چیز سر جاش نیست , حالا شما باید مثلا لباس سفیدتون رو پیدا کنید , ایا می تونید ؟؟!!!
پیدا کردن توی اعدادی که هیچ نظمی ندارند هم به همین صورت هست