در این قسمت تیم کدگیت را با آموزش جستجوی دودویی در سی پلاس پلاس همراهی کنید. ابتدای این آموزش الگوریتم جستجوی دودویی را توضیح داده سپس به پیاده سازی این الگوریتم در سی پلاس پلاس می پردازیم. همچنین پیش نیاز های این آموزش عبارتند از:
الگوریتم جستجوی دودویی
الگوریتم جستجوی دودویی : تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود و یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد.
جستجوی دودویی فقط در آرایه های مرتب استفاده می شود.در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود اگر با این خانه برابر بود جستجو تمام می شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می شود(فرض کرده ایم آرایه به صورت صعودی مرتب شده است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه های آرایه ادامه می یابد. جستجوی دودویی نمونه‌ای از الگوریتمهای تقسیم و غلبه می‌باشد.
پیاده جستجوی دودویی در سی پلاس پلاس
حال نوبت پیاده سازی رسیده است. برای پیاده سازی جستجوی دودویی در سی پلاس پلاس اول نیاز داریم که خانه های آرایه ما sort باشد. ما در این قسمت فرض می کنیم آرایه ورودی ما مرتب است و نیاز به نوشتن مرتب سازی توسط ما ندارد.
حال یک برنامه مینویسیم که جست و جوی دودویی ما درون آن باشد. اسم آن را binary search میگذاریم. در این برنامه دو تابع قرار دارد: 1. Main 2. Binarysearch. این توابع از اسمشان کاربردشان معلوم است نیاز به توضیح اضافی ندارد!!! کد این توابع به صورت زیر است:
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void) {
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("Element is not present in array");
else
printf("Element is present at index %d", result);
return 0;
}
کد جستجوی دودویی در سی پلاس پلاس به این صورت است که ابتدا ما یک آرایه تعریف میکنیم. آرایه ما خود مرتب است. بعد از تعریف آرایه، تابع جستجوی دودویی در سی پلاس پلاس را صدا میزنیم تا عدد 10 را پیدا کند. در صورتی که پیدا شد اندیس آن خانه را در آرایه به برمیگرداند و اگر نبود 1- برمیگرداند.
در تابع جستجوی دودویی در سی پلاس پلاس یک متغییر mid داریم که وسط آرایه است. همانطوری که گفته شد ابتدا چک میکنیم که عددی به دنبال آن هستیم با خانه وسط یکی است یا خیر.
if (arr[mid] == x)
return mid;
اگر حالت گفته شد اتفاق نیفتاد باید به جست و جو ادامه بدهیم. اگر عدد که به دنبال آن هستیم بزرگتر از خانه وسط بود سمت راست آرایه را جست و جو میکنیم.
return binarySearch(arr, mid + 1, r, x);
در غیر این صورت سمت چپ به دنبال آن میرویم.
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
قبل از هر کاری هم یک بررسی کوچک میکنیم ببینیم خانه ای برای جست و جو باقی مانده است یا نه!!!!
if (r >= l)
سلام خوبین
میخواهم تمام درس های سی پلاس پلاس شما را دانلود کنم و بخوانم آیا رایگان استیش ؟
و شما از صفر تا پشرفته سی پلاس پلاس آموزش ساختید ؟
سلام. دروس درون سایت رایگان است. شما می توانید سورس آموزش های ما را دانلود و از آن استفاده گنید. هم چنین توضیح کدها نیز قرار داده شده است.