پیاده سازی جستجوی دودویی به زبان سی شارپ

امروز درباره ی الگوریتم جستجوی دودویی صحبت خواهیم کرد. یکی از انواع الگوریتم های تقسیم و جداسازی میباشد که در هر گام تعداد اطلاعات های مورد جستجو را نصف میکند و پیچیدگی زمان متوسط را صفر میکند (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);
           }
      }
 }