>> ROB BOWDEN: مرحبا، أنا روب.
كيف يمكننا توظيف البحث الثنائي؟
دعونا معرفة ذلك.
لذلك، لاحظ أن هذا البحث ونحن في طريقنا لتنفيذ بشكل متكرر.
هل يمكن أيضا تنفيذ البحث الثنائي تكرارا، حتى إذا كنت فعلت ذلك،
هذا ما يرام تماما.
>> الآن أولا، دعونا نتذكر ما وتهدف المعايير إلى البحث أن يكون.
هنا، ونحن نرى قيمة كثافة العمليات، والتي هي من المفترض أن تكون قيمة المستخدم
تبحث عنه.
ونحن نرى القيم كثافة مجموعة، والتي هو مجموعة التي نحن
البحث عن القيمة.
ونحن نرى ن الباحث، الذي هو طول مجموعة لدينا.
>> الآن، أول شيء أولا.
نحن تحقق لمعرفة ما إذا كان n يساوي 0، في هذه الحالة نعود كاذبة.
ان مجرد القول اذا كان لدينا فارغة مجموعة، قيمة هو واضح ليس في
مجموعة فارغة، حتى نتمكن من العودة كاذبة.
>> الآن، ونحن فعلا تريد أن تفعل ثنائي البحث جزءا من البحث الثنائي.
لذا، نريد أن نجد وسط عنصر من هذه المجموعة.
هنا، ونحن نقول منتصف يساوي ن تقسيم بنسبة 2، منذ منتصف العنصر هو
سيكون طول مجموعة لدينا مقسوما على 2.
الآن نحن في طريقنا للتحقق لمعرفة ما إذا كان العنصر منتصف يساوي قيمة نحن
تبحث عنه.
إذا كان الأمر كذلك القيم المتوسطة يساوي قيمة، ونحن يمكن العودة الحقيقية منذ وجدنا
قيمة في مجموعة لدينا.
>> ولكن إذا لم يكن ذلك صحيحا، والآن يتعين علينا القيام به في العودية
خطوة من البحث الثنائي.
نحن بحاجة للبحث إما إلى تبقى من مجموعة أو ل
وسط مجموعة.
حتى هنا، ونحن نقول إذا كانت القيم في المنتصف هي أقل من القيمة، وهذا يعني أن قيمة
كان أكبر من الوسط من الصفيف.
لذلك يجب أن تكون قيمة لليمين العنصر الذي نحن ننظر فقط في.
>> حتى هنا، ونحن في طريقنا لل بحث بشكل متكرر.
وسوف نبحث في ما نقوم بتمرير لهذا في الثانية.
ولكن ونحن في طريقنا للبحث في حق العنصر الوسط.
وفي حالة أخرى، وهذا يعني أن وكان أقل قيمة من منتصف
مجموعة، وهكذا نحن في طريقنا للبحث إلى اليسار.
الآن، اليسار ستكون أسهل قليلا للنظر في.
لذلك، نرى هنا أننا متكرر داعيا البحث حيث أول
الحجة هي، مرة أخرى، قيمة نحن نبحث أكثر.
الحجة الثانية ستكون في مجموعة أننا كانوا يبحثون انتهى.
والعنصر الأخير الآن وسط.
تذكر المعلمة الأخيرة هي كثافة العمليات لدينا ن، لذلك هذا هو طول مجموعة لدينا.
>> في المكالمة العودية للبحث، ونحن يقولون الآن أن طول
مجموعة هو الوسط.
لذلك، إذا كان لدينا مجموعة من حجم 20، ونحن البحث في الفهرس 10، منذ منتصف هو
20 مقسومة على 2، وهذا يعني أننا ويمر 10 كما جديدة
طول مجموعة لدينا.
تذكر أنه عندما يكون لديك مجموعة طول 10، وهذا يعني صالحة
العناصر هي في مؤشرات من 0 إلى 9.
لذلك هذا هو بالضبط ما نريد أن لدينا مجموعة وتحديد تحديث - اليسار
مجموعة من العنصر الوسط.
>> لذلك، تتطلع الى الحق هو من الصعب بعض الشيء.
الآن أولا، دعونا النظر في طول من مجموعة إلى يمين
العنصر الوسط.
لذلك، إذا كان لدينا مجموعة من حجم ن، ثم وسوف تكون مجموعة جديدة من حجم ن ناقص
وسط ناقص 1.
لذلك، دعونا نفكر ن ناقص الوسط.
>> مرة أخرى، إذا كانت مجموعة من حجم 20 و نحن القسمة 2 للحصول على الوسط،
حتى منتصف هو 10، ثم ن ناقص المتوسطة سوف تعطينا 10، حتى 10
العناصر إلى يمين الوسط.
ولكن لدينا أيضا هذا ناقص 1، لأننا لا نريد أن
وتشمل الوسط نفسه.
حتى ن ناقص الوسط ناقص 1 يعطينا إجمالي عدد العناصر إلى اليمين
المؤشر الوسطى في صفيف.
>> الآن هنا، أن نتذكر أن الوسط المعلمة هي القيم صفيف.
حتى هنا، ونحن تمرير تحديث القيم صفيف.
هذا بالإضافة إلى القيم المتوسطة هو زائد 1 قائلا في الواقع استدعاء متكرر
البحث، ويمر في مجموعة جديدة، حيث يبدأ مجموعة جديدة في الوسط
زائد واحد من قيمنا الأصلية صفيف.
>> بناء جملة بديل لذلك، الآن بعد أن كنت قد بدأت لمعرفة مؤشرات، هي
قيم العطف المتوسطة بالإضافة إلى 1.
لذلك، والاستيلاء على عنوان الوسط بالإضافة إلى عنصر واحد من القيم.
>> الآن، إذا لم تكن مريحة تعديل مجموعة من هذا القبيل، كنت
ويمكن أيضا أن نفذت باستخدام هذه وظيفة مساعد متكررة، حيث
أن يأخذ وظيفة مساعد مزيد من الحجج.
وذلك بدلا من مجرد أخذ القيمة، مجموعة، وحجم المصفوفة،
وظيفة مساعد قد يستغرق أكثر الحجج، بما فيها قيمة المؤشر أقل
ان كنت يهتمون في مجموعة ومؤشر العليا التي يهمك
حول مجموعة.
>> وهكذا تتبع كل من أقل مؤشر ومؤشر العليا، لم تقم بذلك
تحتاج إلى تعديل من أي وقت مضى مجموعة القيم الأصلية.
يمكنك متابعة فقط ل استخدام القيم صفيف.
ولكن هنا، لاحظ أننا لا نحتاج مساعد تعمل طالما نحن
على استعداد لتعديل الأصلي مجموعة القيم.
ونحن على استعداد لتمرير في على القيم التي تم تحديثها.
>> الآن، ونحن لا يمكن البحث الثنائي على صفيف هو غير مصنفة.
لذلك، دعونا الحصول على هذا تسويتها.
الآن، لاحظ هذا النوع هو الماضيين المعلمات الباحث القيم، والذي هو
مجموعة أننا الفرز، وكثافة العمليات ن، الذي هو طول المصفوفة التي
نحن الفرز.
لذلك، وهنا نريد أن تنفيذ خوارزمية الفرز
وهذا هو س ن المربعة.
هل يمكن أن تختار نوع فقاعة، واختيار نوع أو نوع الإدراج، أو
بعض نوع آخر ليس لدينا ينظر في الصف.
ولكن هنا، ونحن في طريقنا لل استخدام اختيار نوع.
>> لذلك، ونحن في طريقنا للتكرار على مجموعة بأكملها.
حسنا، هنا نرى أننا بالتكرار من 0 إلى n ناقص 1.
لماذا ليست كل وسيلة تصل إلى ن؟
حسنا، إذا كنا بالفعل فرز أول ن ناقص 1 العناصر، ثم
العنصر الأخير جدا ما يجب أن يكون بالفعل في المكان الصحيح، لذلك الفرز على
مجموعة بأكملها.
>> الآن، وتذكر كيف اختيار يعمل الفرز.
ونحن في طريقنا للذهاب على مجموعة كاملة تبحث عن قيمة الحد الأدنى في
مجموعة والعصا التي في البداية.
ثم ونحن في طريقنا للذهاب على كامل مجموعة تبحث مرة أخرى للمرة الثانية
أصغر عنصر، والعصا التي في المرتبة الثانية في
مجموعة، وهلم جرا.
لذلك، وهذا ما يقوم به هذا.
>> هنا، ونحن نشهد أننا تحديد الحد الأدنى الحالي
قيمة للمؤشر ط ال.
ذلك على التكرار الأول، ونحن في طريقنا للنظر في قيمة الحد الأدنى لتكون
بداية مجموعة لدينا.
ثم، ونحن في طريقنا لتكرار عبر ما تبقى من مجموعة، والتحقق ل
معرفة ما إذا كان هناك أي عناصر أصغر من واحد أننا حاليا
النظر في الحد الأدنى.
>> حتى هنا، تقدر ي زائد واحد - وهذا أقل من ما نحن عليه حاليا
النظر في الحد الأدنى.
ثم ونحن في طريقنا لاستكمال ما نعتقد هو الحد الأدنى ل
مؤشر ي زائد 1.
لذلك، فعل ذلك عبر مجموعة كاملة، وبعد هذا للحلقة، والحد الأدنى
وينبغي أن يكون الحد الأدنى للعنصر من موقف ط عشر في الصفيف.
>> مرة واحدة لدينا ذلك، فإننا يمكن مبادلة قيمة الحد الأدنى في موقف ط ال
في صفيف.
لذلك هذا هو مجرد تبادل القياسية.
نقوم بتخزين في قيمة مؤقتة - قيمة ط عشر في مجموعة -
وضعت في قيمة ط ال في مجموعة و قيمة الحد الأدنى الذي ينتمي هناك،
ومن ثم تخزين مرة أخرى إلى حيث قيمة الحد الأدنى الحالي كان ليكون
قيمة ط عشر في مجموعة، وذلك أننا لم يخسر عليه.
>> لذلك، التي لا تزال على التكرار التالي.
سنبدأ تبحث عن الثاني قيمة الحد الأدنى وإدراج ذلك في
المركز الثاني.
على التكرار الثالث، ونحن سوف ننظر ل قيمة الحد الأدنى الثالث وإدراج
أن في المركز الثالث، وهكذا على حتى يكون لدينا مجموعة وفرزها.
اسمي روب، وهذا وكان اختيار نوع.