الگوریتم جستجوی دودویی (Binary Search)

  • یکشنبه ۲۱ مهر ۱۳۹۸
  • بازدید ۱۴,۳۶۳ نفر

تصویر binary-search-algorithm_7273 الگوریتم جستجوی دودویی (Binary Search)

الگوریتم جستجوی دودویی (Binary Search)

الگوریتم جستجوی دودویی (Binary Search) در هر گام از جستجو محدوده جستجو را به نصف کاهش می دهد. روش کار به این صورت است که ابتدا عنصر مورد نظر با عنصر خانه وسط مقایسه می شود، اگر با مقدار این خانه برابر بود (بهترین حالت) جستجو تمام می شود. اگر مقدار عنصر مورد نظر از مقدار عنصر خانه وسط بزرگتر بود، بخش بالایی به دو قسمت تقسیم می شود و جستجو در بخش بالایی آرایه ادامه می یابد. اما اگر مقدارش از مقدار عنصر خانه وسط کوچکتر بود، بخش پایینی به دو قسمت تقسیم می شود و جستجو در بخش پایینی آرایه ادامه پیدا می کند. این عملیات تا زمانی که همه عناصر آرایه بررسی شوند، یا عنصر مورد نظر پیدا شود، ادامه می یابد.

تصویر binary_search_7273 الگوریتم جستجوی دودویی (Binary Search)

مسئله

با توجه به آرایه مرتب داده شده (arr[])، تابعی بنویسید که عنصر x را در آرایه جستجو کند.

مثال

راه حل ساده برای حل این مسئله استفاده از الگوریتم جستجوی خطی (linear search) خطی با پیچدگی زمانی O(n) است. یک راه حل دیگر برای این مسئله استفاده از الگوریتم جستجوی باینری (binary search) است. پیچیدگی زمانی الگوریتم باینری سرچ، O(Log n) است و فقط در آرایه های مرتب شده می تواند مورد استفاده قرار گیرد.

حل

در این الگوریتم فقط با یک مقایسه، نصف آرایه از محدوده جستجو خارج می شود.

  • مقایسه x با عنصر وسط آرایه.
  • اگر مقدار x و عنصر وسط برابر بود، اندیس آن بازگردانده می شود.
  • در غیر این صورت، اگر مقدار x از مقدار عنصر وسط بزرگتر باشد، یعنی x در صورت وجود داشتن، در بخش بالایی است. بنابراین در گام بعدی بخش بالایی جستجو می شود.
  • اما اگر x کوچکتر از عنصر وسط باشد، بخش پایینی جستجوی می شود.
  • اگر x پیدا نشود، مقدار -1 بازگردانده می شود.

پیاده سازی الگوریتم جستجوی دودویی به صورت بازگشتی:

امتحان کنید

خروجی:

پیاده سازی الگوریتم جستجوی باینری به صورت عادی (حلقه while):

امتحان کنید

خروجی:

پیچدگی زمانی

پیچدگی زمامی الگوریتم جستجوی باینری را می توان به شکل زیر نوشت:

ثبت نظر
ریفریش کنید!
نظرات کاربران (۲ مورد)
  1. تصویر آواتار کاربر 0
    sara دوشنبه , 30 تیر

    تابع پایتونش چجوری نوشته می شه ؟

    • تصویر آواتار کاربر 124
      AmRoدوشنبه , 30 تیر

      سلام...داخل انجمن مطرح کنید...تا کسانی که میتونن کمکتون کنن.