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

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

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

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

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

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

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

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

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

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

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

لذلك نحن حساب منتصف بواسطة مضيفا 0 بالاضافة الى 14 مقسومة على 2؛ منتصف جميلة واضحة. ويمكننا القول أن نقطة الوسط هو الآن 7. لذلك هو 15 ما كنت تبحث عنه؟ لا ليس كذلك. نحن نبحث عن 19. ولكننا نعرف أن 19 أكبر من ما وجدناه في الوسط. 

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

والآن، نذهب أكثر من ذلك مرة أخرى. نحسب نقطة الوسط الجديد. 8 زائد 14 هو 22، مقسوما على 2 هو 11. هذا هو ما نبحث عنه؟ لا ليس كذلك. نحن نبحث عن قيمة هذا أقل من ما وجدناه فقط. لذلك نحن في طريقنا للتكرار العملية مرة أخرى. ونحن في طريقنا إلى تغيير نقطة نهاية ل يكون مجرد ليسار منتصف. حتى نقطة النهاية الجديدة يصبح 10. والآن، وهذا هو الجزء الوحيد من مجموعة لدينا من خلال لفرز. لذلك علينا القضاء الآن 12 من 15 عناصر. ونحن نعلم أنه إذا 19 موجود في مجموعة، فإنه يجب أن يكون موجودا في مكان ما بين عنصر عدد (8) والعنصر رقم 10. 

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

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

فما هي الخطوة الأولى؟ حساب منتصف من المجموعة الحالية. ما هي نقطة الوسط من المجموعة الحالية؟ حسنا، انها 7، أليس كذلك؟ 14 زائد 0 مقسوما على 2 من 7. 15 ما كنت تبحث عنه؟ لا. انها قريبة جدا، ولكن نحن نبحث عن قيمة أكبر قليلا من ذلك. 

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

الآن، نكرر عملية واحدة لمزيد من الوقت. حساب منتصف الجديد. 8 زائد 14 هو 22، مقسوما على 2 هو 11. هو 23 ما كنت تبحث عنه؟ للاسف لا. نحن نبحث عن قيمة أقل من 23. وحتى في هذه الحالة، نحن ذاهبون لتغيير نقطة النهاية ليكون مجرد على يسار منتصف الحالي. منتصف الحالي هو 11، و ولذا فإننا سوف تحديد نقطة نهاية جديدة للمرة القادمة ونحن نمضي من خلال هذه العملية إلى 10. 

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

ما هو منتصف هذه المجموعة؟ كذلك، فإنه يبدأ في 8، فإنه ينتهي في 8، منتصف هو 8. غير أن ما نبحث عنه؟ الذي نبحث عنه 17؟ لا، نحن نبحث عن 16. حتى إذا كان موجودا في مجموعة، فإنه يجب أن يكون موجودا في مكان ما إلى اليسار من ما نحن فيه حاليا. فما نحن فاعلون؟ حسنا، سنقوم بتعيين نقطة النهاية ليكون مجرد على يسار منتصف الحالي. لذلك سنقوم بتغيير نقطة النهاية إلى 7. هل ترى ما فقط حدث هنا، على الرغم من؟ ننظر هنا الآن. 

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

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

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

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

أنا دوغ ويد. هذا هو CS 50.