أجهزة الكمبيوتربرمجة

البحث الثنائي - واحدة من أسهل الطرق لإيجاد عنصر في مجموعة

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

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

لذا، ما هو مبدأ عمل هذه الطريقة؟ على الفور أن أقول أن البحث الثنائي يعمل ليس في أي مجموعة، ولكن فقط على مجموعة فرزها من الأرقام. في كل خطوة تتخذ العنصر الأوسط من مجموعة (اي عدد العنصر). إذا كان المطلوب عدد أكبر من المتوسط، ثم كل ما تبقى، وهذا هو أقل من الخلية المتوسط، يمكن التخلص منها وعدم النظر فيها. وعلى العكس، إذا كانت أقل من المتوسط - بين هذه الأرقام إلى اليمين، لا يمكنك البحث. ثم حدد منطقة جديدة للبحث، حيث العنصر الأول سيكون العنصر الأوسط من مجموعة كاملة، وآخر والإرادة الماضي. فإن متوسط عدد من الحقل الجديد سيكون ¼ من كل قطاع، وهذا هو، (العنصر الأخير + العنصر الأوسط من مجموعة كاملة) / 2. مرة أخرى، يتم تنفيذ العملية نفسها - مقارنة مع متوسط عدد المصفوفة. إذا كانت قيمة الهدف أقل من المتوسط، ونحن نرفض الجانب الأيمن، وكذلك تفعل بعد ذلك، حتى أن هذا العنصر المتوسط ليس المطلوب الآن.

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

وهي مجموعة من 1 إلى ساعة تحت اسم "MASSIV"، وهو متغير مما يدل على الحدود الدنيا للبحث، ودعا "niz"، والحد الأعلى، ودعا "verh"، فإن متوسط مصطلح البحث - "sredn". والعدد المطلوب - "ISK".

لذلك، علينا أولا تعيين الحد العلوي والسفلي من نطاق البحث:

niz: = 1؛
verh: = ح + 1؛

ثم تنظيم دورة "حتى أسفل أقل من الحد الأعلى":

في حين niz بدأ

في كل خطوة، نقسم هذا الجزء 2:

sredn: = (niz + verh) شعبة 2. {استخدم شعبة وظيفة، لأن الانقسام دون الباقي}

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

іf sredn = ISK ثم كسر.

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

إذا MASSIV [sredn]> ISK ثم verh: = sredn.

وإذا كان على العكس من ذلك، فإنه يجعل الحدود الدنيا:

آخر niz: = sredn.
ينتهي.

هذا كل ما سيكون في البرنامج.

دعونا ننظر كيف سيبدو طريقة ثنائي في الممارسة العملية. النظر في هذه المجموعة: 1، 3، 5، 7، 10، 12، 18، وسوف تسعى الرقم 12.

في المجموع لدينا 7 عناصر، لذلك فإن الوسيلة الرابعة، وقيمة 7.

1 3 5 7 10 12 18

منذ أكثر من 12، 7، 1.3 و 5 عناصر، يمكننا تجاهل. ثم لدينا عدد 4، 4/2 أي بقايا هو 2. لذلك، وهو عنصر الجديد سيكون بمتوسط 10.

7 10 12 18

منذ 12 أكبر من 10، ننبذ 7. يبقى فقط 10 و 12 و 18.

هنا، العنصر الأوسط هو بالفعل 12، وهو العدد المطلوب. اكتمال هذه المهمة - رقم 12 وجدوا.

Similar articles

 

 

 

 

Trending Now

 

 

 

 

Newest

Copyright © 2018 ar.atomiyme.com. Theme powered by WordPress.