عرض مصدر تفتاش جوجي (ألݣوريتم)

{{مقالة زنقة ماكاتخرجش}}
{{مقالة مقطوعة من شجرة}}
{{معلومات ألݣوريتم
|class=[[ألݣوريتم د تفتاش]]
|image=Binary Search Depiction.svg
| caption=متال ديال تطبيق د لألݣوريتم فين لعنصر لهدف هو 7 
|data=[[ليستة (قلدة د الداطا)|ليستة]]
|time=<math>O(\log n)</math>  
|average-time=<math>O(\log n)</math> 
|best-time=<math>O(1)</math> 
|space=<math>O(1)</math>
|optimal=
}}
ف [[لانفورماتيك]]، '''تّفتاش جّوجي''' (ب{{lang-en|Binary search|link=yes}}) هو [[ألݣوريتم د تفتاش]]. كتستعمل ماش تجبر موطاع ديال شي عنصر هدف ف شي ليستة مستفة. تفتاش جوجي كيقارن ديك لعنصر لهدف مع لعنصر لي جا فلوصط ديال ليستة، إدا كانو قد قد سالينا، و يلا كان لهدف صغير من لوصط، كيفتّش ف نص د شْمال (ليستة مستفة من صغير ن لكبير من شمال ن ليمن) د ليستة، إلا كان لهدف كبير من لوصط كيفتش ف نص د ليمن د ليستة. بهاد طريقة طاية ديال ليستة كتقسم على جوج ف كل دورة ديال ل[[ألݣوريتم]]. هنا من جا لإسم ديالو.

تعقيد ف لوقت ديالو هو<math>O(\log n)</math> فين <math>n</math> هو طاي د ليستة.<ref>{{مرجع ويب
|url=https://www.geeksforgeeks.org/binary-search/
|title=Binary Search - Data Structure and Algorithm Tutorials
|date=2014-01-28
|website=GeeksforGeeks
|language=en-US
|accessdate=2023-10-26
|archive-url=https://web.archive.org/web/20231026044908/https://www.geeksforgeeks.org/binary-search/
|archive-date=2023-10-26
|url-status=live
}}</ref> تّفتاش جّوجي سرع من [[تفتاش خطي|تفتاش لخطي]] (تعقيد ف لوقت ديالو <math>O(n)</math>) من غير بنسبة ن ليستات قصارين. ولكن لّيستة خاص ضروري تكون مستفة ماش يتطبق هاد لألݣوريتم بينما تّفتاش لخطي كيخدم فجميع لحالات.

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

<syntaxhighlight lang="python" line="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

</syntaxhighlight>

== تطبيق مسكسف ==

=== لحساب  د <math>\sqrt2</math> بتفتاش جوجي ===
<math>\sqrt2</math> عدد ماشي جدري، يعني ميمكنشي نكتبوه على شكل   <math>\dfrac{a}{b}</math> معا <math>a \in \Z,b \in \N^*</math> ولاكين يمكنا نقربولو بشحال ما بغينا و نجبرو تقريب ديالو على شكل عداد ب لفاصلة.

أنسمّيو <math>x</math>  تّقريب ديال <math>\sqrt2</math> بدقة ديال <math>\epsilon</math> يعني <math>|\sqrt2-x| \leq \epsilon</math>.  عارفين بلي <math>0 \leq x \leq 2</math>   فهاد لحالة ليستة لمستفة هي <math>[0,2]</math> ولعنصر الهدف هو <math>x</math>. <syntaxhighlight lang="python" line="1">

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

</syntaxhighlight>
ف [[پايطون]] ما يمكناشي نفوتو دقة ديال <math>\epsilon = 10^{-15}</math>  تقريبا.

== مصادر ==
{{عيون}}
{{زريعة}}
{{قلدات د الداطا و ألڭوريتمات}}
{{ضبط مخازني}}

[[تصنيف:ألݣوريتم]]
[[تصنيف:ألݣوريتم د تفتاش]]
[[تصنيف:2]]
[[تصنيف:مقالات فيها مصدر و 3000 بايت]]
[[تصنيف:مقالات ب عناوين فيها نيولوجيزم]]