تم تنفيذ خوارزمية البحث الثنائي في Go

كيفية تنفيذ خوارزمية البحث الثنائي في Go

بحث ثنائيهي خوارزمية بسيطة للعثور على عنصر في ملفمجموعة مرتبة، وعادة ما يشار إليها كعينة رمز للدراسة عند تعلم لغة برمجة جديدة.

الكفاءة

إنها فعالة للغاية:

  • وقت:O (تسجيل ن)، في أسوأ الأحوال لوغاريتمي
  • فضاء:0(1)يستغرق وقتًا ثابتًا

نظرية

بالنظر إلى مصفوفة مرتبة ، نختار العنصر Y في المنتصف ونقارنه بالقيمة المستهدفة X.

إذا تطابق Y مع X ، فإننا نعيد الموضع Y ونخرج.

نحدد ما إذا كان X <Y ، في هذه الحالة نتجاهل الجانب الأيمن ، ونذهب في منتصف الجانب الأيسر ، ونكرر نفس العملية على النحو الوارد أعلاه.

ينتهي البحث عندما تتطابق Y أخيرًا مع X. إذا لم يحدث ذلك ، فإننا نعيد الموضع الذي كان من الممكن أن يتخذه X إذا كان في المصفوفة.

التنفيذ

نحن محظوظون ، توفر مكتبة Go القياسية تطبيقًا ثنائيًا للشجرةsortالحزمة ، فيsort.Search().

دعنا نرى استخدام API ، كما هو مأخوذ من وثائق الحزمة ، حتى نعرف ماذاsort.Searchيجب أن تعود:

package main

import ( “fmt” “sort” )

func main() { a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55} x := 6

<span style="color:#a6e22e">i</span> <span style="color:#f92672">:=</span> <span style="color:#a6e22e">sort</span>.<span style="color:#a6e22e">Search</span>(len(<span style="color:#a6e22e">a</span>), <span style="color:#66d9ef">func</span>(<span style="color:#a6e22e">i</span> <span style="color:#66d9ef">int</span>) <span style="color:#66d9ef">bool</span> { <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">&gt;=</span> <span style="color:#a6e22e">x</span> })
<span style="color:#66d9ef">if</span> <span style="color:#a6e22e">i</span> &lt; len(<span style="color:#a6e22e">a</span>) <span style="color:#f92672">&amp;&amp;</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">i</span>] <span style="color:#f92672">==</span> <span style="color:#a6e22e">x</span> {
    <span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"found %d at index %d in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">i</span>, <span style="color:#a6e22e">a</span>)
} <span style="color:#66d9ef">else</span> {
    <span style="color:#a6e22e">fmt</span>.<span style="color:#a6e22e">Printf</span>(<span style="color:#e6db74">"%d not found in %v\n"</span>, <span style="color:#a6e22e">x</span>, <span style="color:#a6e22e">a</span>)
}

}

sort.Searchإرجاع فهرسi، ونحتاج فقط إلى التأكد من احتواء هذا الفهرس بالفعلx.

بالطبع نريد أن نعرف كيف يتم تنفيذ ذلك داخليًا. نظرًا لأن المكتبة القياسية مكتوبة بلغة Go ، ومفتوحة المصدر ، فمن السهل حقًا معرفة كيفية القيام بذلكsort.Searchتم تنفيذه:

func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := i + (j-i)/2 // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}

دعنا نقسمها:

إعطاء مصفوفة بطولn، ووظيفة المقارنةf(التي تقيم داخلياx >= a[h]) ، نبدأ في تكرار المصفوفةa.

دعنا نستخدم القيم الفعلية التي نستخدمها في المثال ، فمن السهل إظهار ما يحدث.

البيانات:

a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
x := 6

التكرار 1:

  • iيكون0وjيكون9.
  • hيحسب على أنه(0 + (9-0) / 2)=4
  • a[h]يكون15. هذا يعني أننا ننفذj = h

التكرار 2:

  • iيكون0وjيكون4.
  • hيحسب على أنه(0 + (4-0) / 2)=2
  • a[h]يكون6. وجدنا موقفx، هذا يعني أننا نعودh = 2

البحث عن ترتيب عكسي

حيث يمكننا تمرير وظيفة إلىsort.Search، من السهل البحث في مصفوفة مرتبة بالترتيب العكسي ، مثل

a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
x := 6

عن طريق تمرير وظيفة تقارنa[i] <= xبدلا منa[i] >= x.

i := sort.Search(len(a), func(i int) bool { return a[i] <= x })

المزيد من دروس Go: