int RecursiveBinarySearch(int a[], int first, int last, int key)
{
if (first > last)
return -1;
int i = (first + last) / 2;
if (key == a[i])
return i;
else if (key < a[i])
return RecursiveBinarySearch(a, first, i - 1, key);
else
return RecursiveBinarySearch(a, i + 1, last, key);
}
پارامتر a آرایه ای است که جستجو داخلش انجام میشه و طبق پیشفرض جستجوی دو دویی این آرایه باید از قبل بصورت صعودی (از کوچک به بزرگ) مرتب شده باشه وگرنه جستجوی دو دویی قابل انجام نیست.
پارامتر first اندیس شروع محدوده ای است که در آرایه جستجو انجام میشه، اگر قراره جستجو از ابتدای آرایه شروع بشه، باید مقدار first برابر 0 باشه.
پارامتر last اندیس انتهای محدوده ای است که در آرایه جستجو انجام میشه، اگر قراره جستجو تا انتهای آرایه n عضوی انجام بشه، باید مقدار last برابر n - 1 باشه.
پارامتر key مقداری است که جستجو برایش انجام میشه.
اگر مقدار مورد نظر پیدا شد، تابع اندیس مورد پیدا شده رو بر می گردونه، وگرنه مقدار 1- به نشانه عدم موفقیت در جستجو برگردونده خواهد شد.
مثال، جستجو در بین اعداد اول کوچکتر از 100، شامل 25 عدد :
کد:
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
int RecursiveBinarySearch(int a[], int first, int last, int key)
{
if (first > last)
return -1;
int i = (first + last) / 2;
if (key == a[i])
return i;
else if (key < a[i])
return RecursiveBinarySearch(a, first, i - 1, key);
else
return RecursiveBinarySearch(a, i + 1, last, key);
}
int main()
{
int a[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37
, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int key;
cout << "Please enter a number : ";
cin >> key;
int i = RecursiveBinarySearch(a, 0, 24, key);
cout << "Index = " << i << endl;
getch();
return 0;
}
بله، کلا جستجوی دو دویی (باینری) همیشه بر مبنای استراتژی تقسیم و حل ئه. بهش دو دویی می گویند چون در هر مرحله از جستجو
مجموعه ای که جستجو رویش انجام میشه رو دو قسمت تقسیم می کنه و یک قسمت رو رها می کنه.
