امروز درباره ی الگوریتم جستجوی دودویی صحبت خواهیم کرد. یکی از انواع الگوریتم های تقسیم و جداسازی میباشد که در هر گام تعداد اطلاعات های مورد جستجو را نصف میکند و پیچیدگی زمان متوسط را صفر میکند (Log n) . بر روی یک آرایه ی مرتب شده کار میکند. در زیر گام های الگوریتم جستجوی دودویی آورده شده است همراه من باشید تا انتها.
گام ۱ : در هر گام کلید جستجو را با مقدار المان میانی آرایه مقایسه میکند.
گام ۲ : هماهنگی کلید در گام ۱ به معنای پیدا شدن المان مشابه است و موقعیت و مقدار آن برگشت داده میشود. در غیر اینصورت گام های ۳ و ۴.
گام ۳ : اگر کلید جستجو از المان میانی کوچکتر باشد , آنگاه الگوریتم کار قبلی خود را اینبار بر ابتدای آرایه تا وسط آن (نیمه پایینی آرایه) تکرار میکند.
گام ۴ : اگر کلید جستجو از المان میانی بزرگتر باشد , آنگاه الگوریتم کار قبلی خود را اینبار بر نیمه ی آرایه تا انتهای آن (نیمه بالایی آرایه) تکرار میکند.
گام ۵ : اگر کلید جستجو در هیچ یک از زیر آرایه های چپ یا راست یافت نشد آنگاه به این معناست که کلید در آرایه وجود ندارد و ” Nil ” میتواند بازگردانده شود.
ما در ابتدا نگاهی می اندازیم به نحوه ی پیاده سازی C# با استفاده از روش های تکرار شونده.
public static object BinarySearchIterative(int[] inputArray, int key, int min, int max) { while (min <=max) { int mid = (min + max) / 2; if (key == inputArray[mid]) { return ++mid; } else if (key < inputArray[mid]) { max = mid - 1; } else { min = mid + 1; } } return "Nil"; }
و این هم یک نمونه بازگشتی از آن.
public static object BinarySearchRecursive(int [] inputArray, int key, int min, int max) { if (min > max) { return "Nil"; } else { int mid = (min+max)/2; if (key == inputArray [mid]) { return ++mid; } else if (key < inputArray [mid]) { return BinarySearchRecursive(inputArray, key, min, mid - 1); } else { return BinarySearchRecursive(inputArray, key, mid + 1, max); } } }
هیچ دیدگاهی نوشته نشده است.