پاسخ : الگوریتم های جستجو
براي محاسبه زمان مورد نياز يك جستجو، بايد به اين نكته توجه كرد كه با هر مقايسه، بازه جستجو نصف مي شود. بدترين حالت زماني است كه داده اصلا پيدا نشود و يا در آخرين مقايسه (زماني كه تنها يك عنصر باقي مانده است) پيدا شود. سوال اينجاست كه چند بار مي توان اندازه آرايه را نصف كرد تا سرانجام به يك عنصر رسيد؟ جستجوي يك عنصر در يك آرايه مرتب به روش دودويي حداكثر نياز به http://vu.um.ac.ir/content/158/ch10/image09.gif مقايسه دارد، كه زمان بسيار مناسبي است. بعنوان مثال در يك آرايه با 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
سلام
اگه مجموعه اعداد ما به صورت مرت شده نباشند به غیر از جستجوی خطی دیگه راه دیگه ای هست؟؟
با سلام به دوست عزیزم :»
اگر اعداد مرتب شده باشد که میدونید خودتون بغیر از خطی چه راه حل های دیگه ای وجود دارد
ولی اگر مرتب شده نباشد , مثل این میمونه که شما توی اتاقتون شلوغ پلوغه و هر چیز سر جاش نیست , حالا شما باید مثلا لباس سفیدتون رو پیدا کنید , ایا می تونید ؟؟!!!
پیدا کردن توی اعدادی که هیچ نظمی ندارند هم به همین صورت هست