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

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

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

n تعداد گره‌ها در یک درخت دودویی کامل است و با استفاده از این فرمول می‌توان آن را یافت ${\displaystyle n=2^{h+1}-1}$

N تعداد گره‌ها در یک درخت دودویی کامل نیز می‌تواند با استفاده فرمول ${\displaystyle n=2L-1}$

تعدادی از لینک‌های تهی (فرزندان غایب از گره‌ها) در یک درخت دودویی کامل از n گره${\displaystyle (n+1)}$

اثبات:

N = تعداد کل گره B = تعداد شاخه‌ها

n₀, n₁, n₂ برای نشان دادن تعداد گره بدون فرزند، تنها یک فرزند و دو فرزند بود

B = n - 1 (از آنجا که تمام گره‌ها به جز گره ریشه از شاخه واحد)

B = n₁ + 2*n₂

n = n₁+ 2*n₂ + 1

n = n₀ + n₁ + n₂

n₁+ 2*n₂ + 1 = n₀ + n₁ + n₂ ==> n₀ = n₂ + 1

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

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

فرض کنید تعداد اعداد ممکن برابر N است، بنابراین ${\displaystyle \lceil \log _{2}N\rceil }$

حتی اگر محدودهٔ اعداد مورد نظر نا محدود باشد (یعنی توسط N محدود نشده باشد) باز هم می‌توان با حداکثر ${\displaystyle 2\lceil \log _{2}k\rceil }$

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

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

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

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

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

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

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

تکرار

یکی از روش ها برای پیدا کردن عنصر مورد نظر x در یک آرایه بنام A روش تکرار است،که مراحل زیر را شامل می شود:

1.دو متغیر i و j به ترتیب مقادیر اولیه 0 و n-1 را می گیرند.(n طول آرایه مورد نظر است.)

2.تا زمانیکه ${\displaystyle i\neq j}$

2.1.متغیر k مقدار ${\displaystyle \left\lceil {\frac {i+j}{2}}\right\rceil }$

2.2.اگر ${\displaystyle A[k]>x}$

2.3.اگر ${\displaystyle A[k]\leq x}$

3.حال ${\displaystyle i=j}$

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
 }

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

static bool BinarySearch(int[] A, int x, int i, int j) {
 if (i> j)
 return false;
 int m = (i + j) / 2;
 if (x> A[m])
 return BinarySearch(A, x, m + 1, j);
 else if (x <A[m])
 return BinarySearch(A, x, i, m - 1);
 else
 return true;
 }

یافتن عنصر سمت چپ

برای یافتن عنصر سمت چپ عنصر مورد نظرمان یعنی T در آرایه A به ترتیب زیر عمل میکنیم:

1.به ترتیب به L و R مقادیر اولیه 0 و n را می دهیم.

2.تازمانیکه L<R باشد مراحل زیر را تکرار میکنیم:

2.1.مقدار ${\displaystyle \left\lfloor {\frac {L+R}{2}}\right\rfloor }$

2.2.اگر ${\displaystyle A[m]<T}$

2.3.اگر ${\displaystyle A[m]\geq T}$

3.مقدار L خروجی داده می شود.

شبه کد زیر این مراحل را نشان می دهد:

binary_search_leftmost(A, n, T):
    L = 0
    R = n
    while L < R:
        m = floor((L + R) / 2)
        if A[m] < T:
            L = m + 1
        else:
            R = m
    return L

یافتن عنصر سمت راست

برای یافتن عنصر سمت چپ عنصر مورد نظرمان یعنی T در آرایه A به ترتیب زیر عمل میکنیم:

1.به ترتیب به L و R مقادیر اولیه 0 و n را می دهیم.

2.تازمانیکه L<R باشد مراحل زیر را تکرار میکنیم:

2.1.مقدار ${\displaystyle \left\lfloor {\frac {L+R}{2}}\right\rfloor }$

2.2.اگر ${\displaystyle A[m]>T}$

2.3.اگر ${\displaystyle A[m]\leq T}$

3.مقدار R-1 خروجی داده می شود.

شبه کد زیر این مراحل را نشان می دهد:

binary_search_rightmost(A, n, T):
    L = 0
    R = n
    while L < R:
        m = floor((L + R) / 2)
        if A[m] > T:
            R = m
        else:
            L = m + 1
    return R - 1