ZAMYLA تشان: أول شيء كنت قد إشعار حول الاكتشاف هو أننا بالفعل وقد مدونة مكتوبة بالنسبة لنا. وهذا ما يسمى كود التوزيع. لذلك نحن لسنا مجرد كتابة منطقتنا رمز من الصفر بعد الآن. بدلا من ذلك، نحن في ملء الفراغات في بعض التعليمات البرمجية الموجودة مسبقا. 

يطالب البرنامج find.c للأرقام لملء كومة قش، يبحث في كومة قش عن إبرة المستخدم المقدمة، وأنه يفعل هذا عن طريق استدعاء نوع و البحث، وظائف محددة في helpers.c. هكذا مكتوب find.c بالفعل. عملك هو لإرسال المساعدين. 

فماذا نحن فاعلون؟ نحن تنفيذ وظيفتين. البحث، والتي ترجع صحيح إذا كانت قيمة وجدت في كومة قش، والعودة false إذا كانت القيمة ليس في كومة قش. ثم نقوم أيضا بتنفيذ الفرز، الذي يفرز مجموعة تسمى القيم. لذلك دعونا معالجة البحث. 

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

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

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

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

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

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

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