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

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

binary search algorithm 7273 تصویر

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

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

binary search 7273 تصویر

مسئله

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

مثال

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

حل

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

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

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

امتحان کنید

خروجی:

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

امتحان کنید

خروجی:

پیچدگی زمانی

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

ثبت نظر
ریفریش کنید!
نظرات کاربران (۰ مورد)

هیچ نظری ثبت نشده است