ما هي المزالق في تنفيذ البحث الثنائي؟

Question

يعد تنفيذ البحث الثنائي أصعب مما يبدو."على الرغم من أن الفكرة الأساسية للبحث الثنائي واضحة نسبيًا، إلا أن التفاصيل قد تكون صعبة بشكل مدهش..." - دونالد كنوث.

ما الأخطاء التي من المرجح أن يتم إدخالها في تطبيق البحث الثنائي الجديد؟

Answer 1

إليك بعض ما يمكنني التفكير فيه:

• أخطاء فردية, ، عند تحديد حدود الفاصل الزمني التالي
• التعامل مع العناصر المكررة, ، إذا كنت تفترض إرجاع العنصر المتساوي الأول في المصفوفة ولكنك بدلاً من ذلك قمت بإرجاع عنصر متساوٍ لاحق
• التدفقات العددية/التجاوزات عند حساب المؤشرات بمصفوفات ضخمة
• العودية ضد غير العودية التنفيذ، وهو اختيار التصميم الذي يجب عليك مراعاته

هل هذا ما يدور في ذهنك؟

Answer 2

كان هذا السؤال سألت للتو مرة أخرى في الآونة الأخيرة.بصرف النظر عن مقولة كنوث "على الرغم من أن الفكرة الأساسية للبحث الثنائي واضحة نسبيًا، إلا أن التفاصيل يمكن أن تكون صعبة بشكل مدهش"، هناك حقيقة تاريخية مذهلة (انظر TAOCP، المجلد 3، القسم 6.2.1) وهي أن البحث الثنائي تم نشره لأول مرة في 1946 لكن أول بحث ثنائي منشور بدون أخطاء كان في عام 1962.وهناك تجربة بنتلي أنه عندما خصص بحثًا ثنائيًا في الدورات التدريبية للمبرمجين المحترفين في أماكن مثل Bell Labs وIBM ومنحهم ساعتين، أفاد الجميع أنهم فعلوا ذلك بشكل صحيح، وعند فحص الكود الخاص بهم، كان 90٪ منهم يعانون من أخطاء - العام بعد عام.

ربما يكون السبب الأساسي وراء ارتكاب العديد من المبرمجين لأخطاء في البحث الثنائي، إلى جانب قانون Sturgeon، هو أنهم ليسوا حذرين بما فيه الكفاية: برمجة اللؤلؤ يقتبس هذا على أنه نهج "اكتب الكود الخاص بك، ثم ارميه على الحائط، واحصل على ضمان الجودة أو اختبار التعامل مع الأخطاء".وهناك مجال كبير للخطأ.ليس فقط الخطأ الفائض الذي تذكره العديد من الإجابات الأخرى هنا، ولكن الأخطاء المنطقية.

فيما يلي بعض الأمثلة على أخطاء البحث الثنائي.وهذا ليس شاملا بأي حال من الأحوال.(كما كتب تولستوي انا كارينينا - "جميع العائلات السعيدة متشابهة؛كل عائلة غير سعيدة هي غير سعيدة بطريقتها الخاصة" - كل برنامج بحث ثنائي غير صحيح هو غير صحيح بطريقته الخاصة.)

باتيس

رمز باسكال التالي مأخوذ من الورقة أخطاء الكتب المدرسية في البحث الثنائي (1988) بقلم ريتشارد إي باتيس.لقد نظر إلى عشرين كتابًا مدرسيًا وتوصل إلى هذا البحث الثنائي (راجع للشغل، يستخدم باسكال فهارس المصفوفات بدءًا من 1):

PROCEDURE BinarySearch (A         : anArray,
                        Size      : anArraySize,
                        Key       : INTEGER,
                        VAR Found : BOOLEAN;
                        VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN         
   LOW := 1;
   High := Size;

   REPEAT
      Index := (Low + High) DIV 2;
      If Key < A[Index]
         THEN High := Index - 1
         ELSE Low  := Index + 1
   UNTIL (Low > High) OR (Key = A[Index]);

   FOUND := (Low <= High)
END;

يبدو طيب؟وهذا فيه أكثر من خطأ.قبل مواصلة القراءة، تحقق مما إذا كان بإمكانك العثور عليها جميعًا.يجب أن تكون قادرًا على تخمين ما يفعله الكود حتى لو كنت ترى باسكال للمرة الأولى.

---

ويصف خمسة أخطاء توجد في العديد من البرامج، وعلى وجه الخصوص ما ورد أعلاه:

خطأ 1:لا يتم تشغيله في زمن O(log n)، حيث n = الحجم.في إطار حماسهم لممارسة البرمجة الصحيحة، يكتب بعض المبرمجين بحثًا ثنائيًا كوظيفة/إجراء، ويمررونه في مصفوفة.(هذا ليس خاصًا بباسكال؛تخيل في لغة C++ تمرير متجه حسب القيمة وليس حسب المرجع.) هذا هو الوقت Θ(n) فقط لتمرير المصفوفة إلى الإجراء، مما يتعارض مع الغرض بأكمله.والأسوأ من ذلك أن بعض المؤلفين يقدمون على ما يبدو أ العودية البحث الثنائي، الذي يمرر مصفوفة في كل مرة، مما يعطي وقت تشغيل هو Θ(n log n).(وهذا ليس بعيد المنال؛لقد رأيت بالفعل رمزًا مثل هذا.)

خطأ 2:يفشل عندما يكون الحجم = 0.قد يكون هذا على ما يرام.ولكن اعتمادًا على التطبيق المقصود، يتم البحث في القائمة/الجدول يمكن يتقلص إلى 0، ويجب التعامل معها في مكان ما.

خطأ 3:يعطي إجابة خاطئة.عندما يبدأ التكرار النهائي للحلقة بـ Low=High (على سبيل المثال:عندما يكون الحجم=1)، فإنه يقوم بتعيين Found:=False، حتى لو Key موجود في المصفوفة.

خطأ 4:فإنه يسبب خطأ كلما Key أقل من أصغر عنصر في المصفوفة.(بعد Index يصبح 1، فإنه يحدد High إلى 0، وما إلى ذلك؛يؤدي إلى خطأ خارج الحدود.)

خطأ 5:فإنه يسبب خطأ كلما Key أكبر من أكبر عنصر في المصفوفة.(بعد Index يصبح Size, ، فإنه يحدد Low إلى الحجم+1 وما إلى ذلك؛يؤدي إلى خطأ خارج الحدود.)

ويشير أيضًا إلى أن بعض الطرق الواضحة "لإصلاح" هذه الأخطاء يتبين أنها خاطئة أيضًا.غالبًا ما تحتوي التعليمات البرمجية الواقعية أيضًا على هذه الخاصية، عندما يكتب المبرمج شيئًا غير صحيح، ويعثر على خطأ، ثم "يصلحه" حتى يتم حله. بدت الصحيح دون التفكير مليا بما فيه الكفاية.

من بين 20 كتابًا مدرسيًا قام بتجربتها، كان هناك 5 منها فقط تحتوي على بحث ثنائي صحيح.وفي الـ 15 المتبقية (يقول 16، من سخرية القدر)، وجد 11 حالة للخطأ 1، وستة حالات للخطأ 2، واثنتين لكل من الخطأين 3 و4، وواحدة للخطأ 5.مجموع هذه الأرقام يصل إلى أكثر من 15 بكثير، لأن العديد منها يحتوي على أخطاء متعددة.

---

مزيد من الأمثلة

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

لنفترض أن لديك دالة متزايدة (غير متناقصة) f:R->R، و(لأنك تريد جذر f، على سبيل المثال)، فأنت تريد العثور على الأكبر t مثل ذلك f(t) < 0.تعرف على عدد الأخطاء التي يمكنك العثور عليها في ما يلي:

float high = INF, low = 0;
while(high != low) {
   float mid = (low + high)/2;
   if(f(mid)>0) high=mid;
   else low=mid;
}
printf("%f", high);

(بعض:قد لا يكون هناك مثل هذا في [0,INF]، إذا f إذا كانت 0 على فترة زمنية فهذا خطأ، لا تقارن أبدًا أرقام الفاصلة العائمة للمساواة، وما إلى ذلك.)

كيفية كتابة البحث الثنائي

لقد اعتدت على ارتكاب العديد من هذه الأخطاء - في العشرات من المرات الأولى التي كتبت فيها بحثًا ثنائيًا (وكان ذلك أثناء مسابقات البرمجة مع ضغط الوقت)، حوالي 30% من الوقت كان هناك خطأ ما في مكان ما - حتى وجدت الطريقة البسيطة لكتابته بشكل صحيح.لم أخطأ في البحث الثنائي منذ ذلك الحين (على ما أذكر).الحيلة بسيطة جدًا:

الحفاظ على ثابت.

ابحث/قرر واوضح بعض الخصائص الثابتة التي تلبيها المتغيرات "المنخفضة" و"العالية" طوال الحلقة:قبل وأثناء وبعد.تأكد من عدم انتهاكه أبدًا.بالطبع تحتاج أيضًا إلى التفكير في شرط الإنهاء.وقد تقدم تفصيل ذلك في الفصل الرابع من هذا الباب برمجة اللؤلؤ أيّ يشتق برنامج بحث ثنائي من الطرق شبه الرسمية.

على سبيل المثال، لتجريد الحالة التي يتم فحصها قليلًا، لنفترض أنك تريد العثور على أكبر قيمة عددية x التي بعض الشرط poss(x) صحيح.حتى هذا الوضوح في تعريف المشكلة هو أكثر مما يبدأ به العديد من المبرمجين.(على سبيل المثال، poss(x) ربما a[x] ≤ v لبعض القيمة v;هذا لمعرفة عدد العناصر الموجودة في المصفوفة التي تم فرزها a هي مبشرة من v, ، على سبيل المثال.) ثم إحدى طرق كتابة البحث الثنائي هي:

int lo=0, hi=n;
//INVARIANT: poss(lo) is true, poss(hi) is false
//Check and ensure invariant before starting binary search
assert(poss(lo)==true);
assert(poss(hi)==false);
while(hi-lo>1) {
    int mid = lo + (hi-lo)/2;
    if(poss(mid)) lo = mid;
    else hi = mid;
}
printf("%d \n",lo);

يمكنك إضافة المزيد من عبارات التأكيد وعمليات التحقق الأخرى، ولكن الفكرة الأساسية هي ذلك لأنك تقوم بالتحديث lo ل mid فقط عندما تعرف ذلك poss(mid) صحيح، يمكنك الحفاظ على ذلك الثابت poss(lo) هو دائما صحيح.وبالمثل، قمت بتعيين hi ل mid فقط عندما poss(mid) غير صحيح، لذلك يمكنك الحفاظ على ذلك الثابت poss(hi) هو دائما كاذبة.فكر في شرط الإنهاء بشكل منفصل.(لاحظ أنه عندما hi-lo هو 1، mid بالضبط مثل lo.لذلك لا تكتب الحلقة كما while(hi>lo), ، أو سيكون لديك حلقة لا نهائية.) في نهاية الحلقة، نضمن لك ذلك hi-lo هو 1 على الأكثر، ولأنك حافظت دائمًا على ثباتك (poss(lo) صحيح و poss(hi) غير صحيح)، لا يمكن أن يكون 0.أيضًا، مرة أخرى بسبب ثباتك، أنت تعرف ذلك lo هي القيمة المراد إرجاعها/طباعتها/استخدامها.هناك طرق أخرى لكتابة البحث الثنائي بالطبع، ولكن الحفاظ على ثابت هو خدعة/نظام يساعد دائمًا.

Answer 3

اقرأ هذا . اختبأ تنفيذ بحث ثنائي جاوة خلل لمدة عشر سنوات تقريبا قبل أن يكتشف أحد ذلك.

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

Answer 4

إذا كان لديك كتاب اللآلئ البرمجة قريب، يجب أن تحقق الفصل 4.

وedit2: كما ورد في التعليقات، يمكنك تحميل مشروع الفصل الأول ذكر موقع المؤلف: <لأ href = "http://www.cs.bell-labs.com/cm/cs/pearls/sketch04 هتمل "يختلط =" نوفولو noreferrer "> http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html

Answer 5

أحد الأسباب الحاسمة لعدم تمكن الأشخاص من تنفيذ البحث الثنائي بشكل صحيح هو أننا لا تصف البحث الثنائي بشكل جيد، فهي مشكلة محددة جيدًا ولكن عادةً لا يتم تعريفها جيدًا.

إحدى القواعد العالمية هي التعلم من الفشل.وهنا يساعد التفكير في الحالات "غير الصالحة" في توضيح المشكلة.ماذا لو كان الإدخال فارغًا؟ماذا لو كان الإدخال يحتوي على نسخ مكررة؟هل يجب أن أقوم بتنفيذه عن طريق اختبار شرطي واحد أو اختبارين (بالإضافة إلى اختبار إضافي للإنهاء المبكر) لكل تكرار؟ومشكلات فنية أخرى مثل التجاوز العددي/التجاوز العددي في مؤشرات الحوسبة وغيرها من الحيل.

الأخطاء التي يمكن تجنبها من خلال وصف المشكلة جيدًا هي الأخطاء الفردية، والتعامل مع العناصر المكررة، كما أشار @Zach Scrivena.

ينظر العديد من الأشخاص إلى البحث الثنائي على أنه العثور على قيمة مستهدفة في ضوء مصفوفة مرتبة.هذه هي الطريقة الثنائية التي يتم بها استخدام، وليس البحث الثنائي في حد ذاته.

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

# (my) definition of binary search:
input: 
    L: a 'partially sorted' array, 
    key: a function, take item in L as argument
prerequisite: 
    by 'partially sorted' I mean, if apply key function to all item of L, we get a 
    new array of bool, L_1, such that it can't be partitioned to two left, right blocks, 
    with all item in left being false, all item in right being true. 
    (left or/and right could be empty)
output: 
    the index of first item in right block of L_1 (as defined in prerequisite). 
    or equivalently, the index of first item in L such that key(item) == True

هذا التعريف يحل بشكل طبيعي المشكلة المكررة.

هناك عادة طريقتان للدلالة على المصفوفات، [] و [، وأنا أفضل الأخيرة، معادلة النهج [) تستخدم زوج (البدء، العد) بدلاً من ذلك.

# Algorithm: binary search
# input: L: a 'partially sorted' array, key: a function, take item in L as argument
    while L is not empty:
        mid = left + (right - left)/2  # or mid = left + count/2
        if key(mid item) is True:
            recede right # if True, recede right
        else:
            forward left # if False, forward left
    return left

وهكذا، إذا قمت بإجراء "إذا كان صحيحا، تراجع (النهاية)" و "إذا كان خطأ، للأمام (البدء)" الجزء الصحيح، لقد انتهيت تقريبًا.اسميها "قاعدة FFTR" للبحث الثنائي. إذا كنت تريد العثور على العنصر الأول، كما في التعريف أعلاه، فسيتم البدء من اليسار، ولكن سيتم البدء من اليمين إذا كنت تريد العثور على العنصر الأخير.إذا كنت تتوافق مع الموضة [)، فإن التنفيذ المحتمل هو،

while left<right:
    mid = left + (right - left)/2
    if key(L(mid)) == True:
        right = mid
    else:
        left = mid+1
    return left

دعونا نتحقق من صحتها بشكل أكبر، من خلال إظهار التقارب أولاً، ثم إظهار الصحة.

التقارب:

whenever left == right, we exit loop (also true if being empty at the first)

so, in the loop, if denote, 

    diff = (right - left)/2, 

    lfstep = 1 + diff/2, 'lfstep' for 'left index forward step size'

    rbstep = diff - diff/2, 'rbstep' for 'right index back (recede) step size'

it can be show that lfstep and rbstep are alway positive, so left and right 
will be equal at last. 

both lfstep and rbstep are asymptotically half of current subarray size, so it's 
of logarithm time complexity.

صحة:

if the input array is empty:
    return the left index;
else:
    if key(mid item) is true:
        "recede right"
        so mid and all item after mid are all true, we can reduce the search range 
        to [left, mid), to validate it, there are two possible cases,
        case 1:
            mid is the first item such that key(item) is True, so there are no true items 
            in new search range [left, mid), so the test will always be false, and we 
            forward left at each iteration until search range is empty, that is  
            [finalleft,mid), since we return finalleft, and finalleft == mid, correctly done!
        case 2:
            there are item before mid such that key(item) is True,
            in this case we just reduce to a new problem of smaller size
    else:
        "forward left"
        mid and all item before mid is false, since we are to find the first true one, 
        we can safely reduce to new search range [mid+1, right) without change the result.

الإصدار المكافئ (البدء، العد)،

while count>0:
    mid = start + count/2
    if key(L[mid]) == True:
        right = mid
    else:
        left = mid+1
return left

كي تختصر, ، إذا كان مطابقًا لاتفاقية [) ،

1. define your key function of your problem, 
2. implement your binary search with "FFTR rule" -- 
    "recede (end) if True ( key(item) == True) else forward (start)" 
    examples:
        if to find a value target, return index or -1 if not found,
        key = lambda x: x>=target, 
        if L[found_index] == target: return found_index
        else: return -1

أما بالنسبة للإنهاء المبكر باختبار إضافي، فلا أعتقد أن الأمر يستحق الأجر، ولكن يمكنك المحاولة.

Answer 6

والفشل في نظر أنه عندما حساب منتصف الفترة الفاصلة بين رقمين قياسيين بجمع القيم العالية والمنخفضة قد يؤدي إلى تجاوز عدد صحيح.

المرجعي

Answer 7

تعد بنية الأنابيب للمعالجات الحديثة أكثر ملاءمة لإجراء عمليات بحث خطية أكثر من إجراء عمليات بحث ثنائية تحتوي على الكثير من القرارات والفروع.

ولذلك مشترك خطأ في الأداء و أ التحسين المبكر (كما تعلمون، هذه هي أصل كل الشرور) يستخدم البحث الثنائي على الإطلاق عندما يكون البحث الخطي البسيط أسرع وبالطبع أبسط.

اعتمادًا على عدد القراءات، حتى فرز البيانات على الإطلاق يمكن أن يجعل الأمور أبطأ.يمكن أن تكون نقطة التعادل بين الخطي والثنائي بسهولة عند 1000 عنصر للمفاتيح البسيطة (على سبيل المثال.أعداد صحيحة 32 بت).