[عزف الموسيقى] 

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

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

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

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

ولكن هناك شرط. البحث الثنائية يمكن البحث فقط من خلال القوائم قبل فرزها. لماذا؟ 

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

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

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

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

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

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

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

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

لأني يساوي 0، العنصر الأول جدا إلى n ناقص 1، وأنت تسير لمقارنة كل قيمة المقبل بعد أن وتجد مؤشر قيمة الحد الأدنى. عندما تجد مؤشر قيمة الحد الأدنى، يمكنك مبادلة أن قيمة مجموعة الحد الأدنى ومجموعة I. 

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

حتى تلك مثالين من نوع الخوارزميات التي يمكن تنفيذها ل برنامج البحث. وبمجرد الانتهاء من الفرز، وكنت قد يتم البحث، الانتهاء. اسمي Zamyla، وهذا هو CS50. 

[عزف الموسيقى]