تفتاش جوجي (ألݣوريتم)

موضيل:مقالة زنقة ماكاتخرجش موضيل:مقالة مقطوعة من شجرة موضيل:معلومات ألݣوريتم ف لانفورماتيك، تّفتاش جّوجي (بموضيل:Lang-en) هو ألݣوريتم د تفتاش. كتستعمل ماش تجبر موطاع ديال شي عنصر هدف ف شي ليستة مستفة. تفتاش جوجي كيقارن ديك لعنصر لهدف مع لعنصر لي جا فلوصط ديال ليستة، إدا كانو قد قد سالينا، و يلا كان لهدف صغير من لوصط، كيفتّش ف نص د شْمال (ليستة مستفة من صغير ن لكبير من شمال ن ليمن) د ليستة، إلا كان لهدف كبير من لوصط كيفتش ف نص د ليمن د ليستة. بهاد طريقة طاية ديال ليستة كتقسم على جوج ف كل دورة ديال لألݣوريتم. هنا من جا لإسم ديالو.

تعقيد ف لوقت ديالو هو$O(\log n)$ فين $n$ هو طاي د ليستة. تّفتاش جّوجي سرع من تفتاش لخطي (تعقيد ف لوقت ديالو $O(n)$) من غير بنسبة ن ليستات قصارين. ولكن لّيستة خاص ضروري تكون مستفة ماش يتطبق هاد لألݣوريتم بينما تّفتاش لخطي كيخدم فجميع لحالات.

لكود ف پايطون

هادا متال ديال لألݣوريتم ف پايطون، هنايا L هي ليستة، target هو لعنصر لهدف. هاد فونكسيون كترجع رقم تستافي ديال لهدف. ليستة مستفة من شمال ن  ليمن (رقم تستافي لول هو 0 و لاخر هو طاي د L ناقص واحد). ادا لهدف مكانش ف ليستة كترجع 1-.

 def binary_search(L, target):
    l, r = 0, len(L)-1
    while l <= r:
        mid = (l+r)//2
        if L[mid] == target:
            return mid
        elif L[mid] > target:
            r = mid - 1
        else:
            l = mid + 1
    return -1

تطبيق مسكسف

لحساب  د $\sqrt{2}$ بتفتاش جوجي

$\sqrt{2}$ عدد ماشي جدري، يعني ميمكنشي نكتبوه على شكل   $\frac{a}{b}$ معا $a\in \mathbb{Z},b\in {\mathbb{N}}^{*}$ ولاكين يمكنا نقربولو بشحال ما بغينا و نجبرو تقريب ديالو على شكل عداد ب لفاصلة.

أنسمّيو

$x$

  تّقريب ديال 

$\sqrt{2}$

بدقة ديال

$ϵ$

يعني

$|\sqrt{2}-x|\le ϵ$

.  عارفين بلي

$0\le x\le 2$

   فهاد لحالة ليستة لمستفة هي

$[0,2]$

ولعنصر الهدف هو

$x$

. 

def sqrt(y, epsilon):
   l, r = 0, y
    mid = (l+r)/2
    while abs(mid**2-y) > epsilon:
        mid = (l+r)/2
        if mid**2 > y:
            r = mid
        elif mid **2 < y:
            l = mid
    return mid

ف پايطون ما يمكناشي نفوتو دقة ديال $ϵ=10^{-15}$  تقريبا.