سلام و عرض ادب
من روش جستجوی دودویی (باینری )را به صورت بازگشتی برای توربو سی پلاس پلاس می خوام؟
ممنون میشم دوستان کمکم کنند.....
حتما به شرایط جستجوی دودویی (باینری) آشنایی دارید، یک آرایه که از قبل کاملا مرتب شده (معمولا بصورت صعودی)
یعنی اگر m < n باشد نباید مقدار عنصر اندیس m بزرگتر از عنصر اندیس n آرایه باشد.
کد زیر یک جستجوی دودویی در آرایه ای از نوع int انجام می دهد، اگر عنصر مورد نظر پیدا شود اندیس آن عنصر در
آرایه برگردانده می شود و اگر پیدا نشود مقدار 1- برگردانده می شود، پارامتر اول مقداری است که دنبالش می گردیم،
پارامتر دوم هم که آرایه ای است که جستجو در آن انجام می شود، پارامتر سوم و چهارم اندیس شروع و پایان جستجو
هستند :
کد:
int Search(int value, int array[], int start, int finish)
{
if (finish < start)
return -1;
int middle = (start + finish) / 2;
if (array[middle] == value)
return middle;
if (array[middle] < value)
return Search(value, array, middle + 1, finish);
return Search(value, array, start, middle - 1);
}
روش کار این است که ابتدا بررسی می کنیم که اندیس های start و finish معتبر باشند، اگر شروع از پایان
بزرگتر باشد یعنی معتبر نیستند و مقدار 1- بازگردانده می شود :
کد:
if (finish < start)
return -1;
آرایه از اندیس start الی finish جستجو می شود، اما ما هر بار بازه جستجو را به دو قسمت تقسیم می کنیم
و یک قسمت را حذف خواهیم کرد، تا زمانی که یا عنصر مورد جستجو در وسط آنها پیدا شود و یا دیگر چیزی برای
جستجو باقی نماند.
در ادامه اندیس وسط بازه جستجو شده را پیدا می کنیم و نام اش را middle قرار می دهیم، در واقع
آرایه را به دو قسمت تقسیم کرده ایم، قسمت قبل از middle از بازه start الی middle - 1 و
قسمت بعد از middle از بازه middle + 1 الی finish :
کد:
int middle = (start + finish) / 2;
اگر مقداری که جستجو می کنیم دقیقا در وسط بازه جستجو شده باشد، اندیس اش middle است
و جستجو خاتمه یافته و اندیس middle بازگردانده می شود :
کد:
if (array[middle] == value)
return middle;
اما اگر مقداری که در وسط بازه جستجو قرار دارد کوچکتر باشد، یعنی قسمتی که قبل از middle قرار دارد
کوچکتر از آن است که جستجو در آنها نتیجه بدهد، پس جستجو را در بخشی که از middle بزرگتر است
ادامه می دهیم، یعنی بازه middle + 1 الی finish . پس به سادگی نصف بازه جستجو را حذف کرده ایم :
کد:
if (array[middle] < value)
return Search(value, array, middle + 1, finish);
در غیر اینصورت حتما مقداری که در وسط بازه جستجو قرار دارد بزرگتر است، یعنی قسمتی که بعد از middle
قرار دارد بزرگتر از آن است که جستجو در آنها نتیجه بدهد، پس جستجو را در بخشی که از middle کوچکتر است
ادامه می دهیم، یعنی بازه start الی middle - 1
کد:
return Search(value, array, start, middle - 1);
اگر آرایه از قبل مرتب باشد جستجوی دودویی می تواند با سرعت فوق العاده ای آرایه بسیار بزرگی را جستجو کند،
مثلا یک آرایه ای که 1208925819614629174706175 عنصر دارد در حداکثر 80 مرحله جستجو می شود.
