براي محاسبه زمان مورد نياز يك جستجو، بايد به اين نكته توجه كرد كه با هر مقايسه، بازه جستجو نصف مي شود. بدترين حالت زماني است كه داده اصلا پيدا نشود و يا در آخرين مقايسه (زماني كه تنها يك عنصر باقي مانده است) پيدا شود. سوال اينجاست كه چند بار مي توان اندازه آرايه را نصف كرد تا سرانجام به يك عنصر رسيد؟ جستجوي يك عنصر در يك آرايه مرتب به روش دودويي حداكثر نياز به مقايسه دارد، كه زمان بسيار مناسبي است. بعنوان مثال در يك آرايه با 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)
علاقه مندی ها (Bookmarks)