الگوریتم جستجوی دودویی

الگوریتم جستجوی دودویی، تکنیکی است برای یافتن یک مقدار عددی از میان مجموعه‌ای از اعداد مرتب. این متد محدودهٔ جستجو را در هر مرحله به نصف کاهش می‌دهد، بنابراین هدف مورد نظر یا به زودی پیدا می‌شود و یا مشخص می‌شود که مقدار مورد جستجو در فهرست وجود ندارد.

جستجوی دودویی نمونه‌ای از الگوریتمهای تقسیم و حل (به انگلیسی: Divide and conquer) می‌باشد.

مقدمه

پیدا کردن اندیس یک عنصر خاص در یک لیست مرتب شده مفید است زیرا با استفاده از اندیس داده شده می‌توان به سایر اطلاعات مربوطه دست یافت.

فرض کنید داده ساختاری شامل مجموعه‌ای از اطلاعات نام٫ آدرس و شماره تلفن و غیره‌است و آرایه ای که نام‌ها را در بر دارد از ۱ تا N شماره گذاری شده‌است، یک در خواست می‌تواند این باشد: شماره فردی به نام X چند است. برای پاسخ دادن به این سوال آرایه مورد نظر باید جستجو شده و اندیس مربوط به نام داده شده در صورت وجود برگردانده شود، در این حالت شماره تلفن ذخیره شده در آرایه تلفن‌ها در این اندیس، همان شماره فرد X است و به همین ترتیب برای آدرس و غیره نیز می‌توان عمل کرد.

مثال

بازی های حدس شماره

این بازی‌های ساده با چیزی شبیه این شروع می‌شوند:" من عددی را بین ۴۰ و ۶۰ در نظر گرفته‌ام و تو آن را حدس می‌زنی و من با این پاسخ‌ها تو را راهنمایی می‌کنم: کمتر، بیشتر و بله!

فرض کنید تعداد اعداد ممکن برابر N است، بنابراین $\lceil\log_2 N\rceil$ سوال لازم است تا عدد مورد نظر پیدا شود چون هر سوال فضای جستجو را نصف می‌کند.

حتی اگر محدودهٔ اعداد مورد نظر نا محدود باشد(یعنی توسط N محدود نشده باشد) باز هم می‌توان با حداکثر $2\lceil \log_2 k \rceil$ مرحله(که K عدد انتخاب شده‌است) عدد مورد نظر را یافت بدین ترتیب که با شروع از یک و دو برابر کردن آن در هر مرحله ابتدا مرز بالایی را پیدا نموده و سپس عدد خواسته شده را پیدا می‌کنیم. به عنوان مثال اگر عدد انتخاب شده ۱۱ باشد ما می‌توانیم ترتیب پرسش‌های زیر را برای پیدا کردن عدد دنبال کنیم: ۱ ← ۲ ← ۴ ← ۸ ← ۱۶ ← ۱۲ ← ۱۰ ← ۱۱.

هم چنین می‌توان این تکنیک را گسترش داد تا شامل اعداد منفی نیز بشود، به عنوان مثال حدس های زیر دنبال می‌شوند تا عدد ۱۳- پیدا شود: ۰ ← ۱- ← ۲- ← ۴- ← ۸- ← ۱۶- ← ۱۲- ← ۱۴- ← ۱۳-.

لیست های کلمات

انسان ها معمولاً ترکیبی از جستجوی دودویی و الگوریتم های جستجوی الحاقی را هنگام جستجوی دفترچه تلفن به کار می‌برند. بعد از حدس اولیه ما از این حقیقت استفاده می کنیم که ورودی ها مرتب اند و درنتیجه سریع تر به هدف می رسیم.مثلاً وقتی به دنبال "کریمی" می گردیم اگر "گنجی" و "قلی پور" پیدا شوند ما می‌توانیم به صفحه‌ای بین حدس های قبلی مراجعه کنیم و اگر مثلاً "کمالی" را نشان می‌داد می دانیم که صفحهٔ مورد نظر جایی بین "قلی پور" و "کمالی" خواهد بود.

تابع

تکرار برای N < 64

برای این که وارد جزئیات تابع شویم باید قراردادهای رسمی تری را تعریف می کنیم.ایده اولیه این است که داده ساختاری وجود دارد که به صورت آرایه A نمایش داده می‌شود، و المان های آن به صورت A(1), A(2),…,A توصیف می‌شوند و به هر ترتیبی قابل دستیابی اند.

داده ساختاری شامل دادهٔ دیگری به نام Key می‌شود، آرایه به گونه‌ای مرتب می‌شود که A(1).Key <= A(2).Key و ... .

هدف این است که مقدار x داده شده و اندیس p پیدا شود به طوری که A(p).Key = x.

برای آغاز محدوده‌ای که باید جستجو شود کل داده هاست که با متغیر های L و R مشخص می‌شود و این مرز ها در هر بار تکرار الگوریتم کاهش می‌یابد.

پیاده سازی

تکرار

Niklaus Wirth این الگوریتم را در پاسکال ارائه کرده است:

 i := 1;
 j := N; {array size: var A : array [1..N] of integer}
 repeat
   k := (i + j) div 2;
   if x > A[k] then
     i := k + 1
   else 
     j := k - 1;
 until (A[k] = x) or (i > j);

بازگشتی

پیاده سازی متداول این تابع توسط الگوریتم بازگشتی زیر می‌باشد:

  BinarySearch(A[0..N-1], value, low, high) {
      if (high < low)
          return -1 // not found
      mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
      if (A[mid] > value)
          return BinarySearch(A, value, low, mid-1)
      else if (A[mid] < value)
          return BinarySearch(A, value, mid+1, high)
      else
          return mid // found
  }

منابع

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.1: Searching an Ordered Table, pp.409–426.
• Kruse, Robert L.: "Data Structures and Program Design in C++", Prentice-Hall, 1999, ISBN 0-13-768995-0, page 280.
• http://en.wikipedia.org/wiki/Binary_search_algorithm

پیوند بیرونی

• NIST Dictionary of Algorithms and Data Structures: binary search
• Binary Search using C++
• Binary Search using PHP