ثنائی تلاش - سب سے آسان طریقوں میں سے ایک ایک صف میں ایک عنصر کو تلاش کرنے کے

اکثر، پروگرامرز، بھی beginners، اعداد کی ایک سیٹ، ایک مخصوص تعداد کو تلاش کرنا ہوگا جس میں نہیں ہے اس حقیقت کے ساتھ سامنا کرنا پڑا. یہ اس مجموعہ ایک صف کہا جاتا ہے. اور یہ میں اشیاء کو تلاش کرنے کے طریقوں کی ایک تہہ موجود ہیں. لیکن ان میں سے سب سے زیادہ سادہ حق پر ایک بائنری تلاش سمجھا جا سکتا ہے. یہ طریقہ ہے کیا ہے؟ اور کس طرح بائنری تلاش کو لاگو کرنے کے لئے؟ پاسکل طرح کے ایک پروگرام کی تنظیم کے لئے سب سے آسان ماحول ہے، اس لیے ہم مطالعہ کرنے کے لئے اس کا استعمال کریں گے.

سب سے پہلے، کا تجزیہ، اس طریقے کے فوائد کیا ہیں، یہ ہے تو ہم سمجھ سکتے ہیں، موضوع کے مطالعہ کا کیا مطلب ہے. تو، چلو کچھ تلاش کرنے کی ضرورت ہے جس میں کم از کم 100000000 عناصر، کی ایک جہت سے ایک صف ہے دو. کورس کے، اس مسئلہ کو آسانی سے ہم صف میں ہیں کہ ان تمام لوگوں کے ساتھ مطلوبہ عنصر موازنہ کریں گے سائیکل استعمال کر رہے ہیں جس میں ایک سادہ لکیری تلاش، کی طرف سے حل کیا جا سکتا ہے. مسئلہ یہ ہے کہ اس خیال کے نفاذ میں بہت زیادہ وقت لگے گا ہے. کئی علاج، اور اصل متن کے تین لائنوں میں ایک سادہ پاسکل پروگرام میں، آپ کو یہ محسوس نہیں کریں گے، لیکن ہم شاخوں اور اچھی فعالیت کی ایک بڑی تعداد کے ساتھ ایک سے زیادہ یا اس سے کم بڑے منصوبوں کے لئے آیا جب، پروگرام زیادہ دیر تک لوڈ کیا جا کرنے کے لئے تیار ہو جائے گا. خاص طور پر کمپیوٹر کے ایک کمزور کارکردگی ہے. لہذا، ایک بائنری تلاش، جس میں کم از کم دو مرتبہ تلاش کے وقت کو کم کر دیتا ہے.

لہذا، اس طریقے کے کام کے اصول کیا ہے؟ فوری طور پر یہ کہنا چاہیے بائنری تلاش کے کام کرتا ہے کہ کسی بھی صف میں نہیں ہے، لیکن صرف اعداد کی ایک کے مطابق کی سیٹ پر. صف میں سے ہر ایک قدم اٹھایا درمیانی عنصر میں (عنصر کی تعداد کا مطلب ہے). اگر ضرورت ہو تو تعداد سے زیادہ ہے اوسط، پھر تمام چھوڑ دیا جاتا ہے کہ اوسط سیل سے کم ہے، ضائع کیا جا سکتا ہے اور وہاں دیکھنے کے لئے نہیں. اس کے برعکس، اوسط سے کم ہے تو - حق کو ان لوگوں کی تعداد کے علاوہ، آپ کو تلاش نہیں کر سکتے. اس کے بعد سب سے پہلے عنصر پوری صف کے وسط عنصر، اور آخری اور آخری گا ہو جائے گا جہاں ایک نئی تلاش علاقے، کو منتخب کریں. نیا میدان کا اوسط نمبر ہے کہ تمام طبقہ، (آخری عنصر + پوری صف کے وسط عنصر) / 2 کے ¼ ہو جائے گا. ایک بار پھر، ایک ہی آپریشن کارکردگی کا مظاہرہ کر رہا ہے - صف کی اوسط تعداد کے ساتھ ایک موازنہ. ہدف قدر اوسط سے کم ہے تو، ہم دائیں طرف کو مسترد کرتے ہیں، اور یہ بھی اب تک اس درمیانی عنصر مطلوبہ نہیں کریں گے، اگلے کرنے کے لئے.

بالکل، یہ بائنری تلاش کے لکھنے کے لئے کس طرح ایک مثال کو دیکھنے کے لئے سب سے بہتر ہے. پاسکل یہاں کسی کو اچھا لگے گا - ورژن اہم نہیں ہے. کی ایک سادہ پروگرام لکھتے ہیں.

اس کا نام "massiv" کے تحت ح 1 کی ایک صف ہے، تلاش کے نچلے حد اشارہ ایک متغیر، "Niz کی" کہا جاتا ہے، اوپری کی حد، "سے verh"، اوسط تلاش کی اصطلاح کہا جاتا ہے - "sredn"؛ اور مطلوبہ تعداد - "ISK".

تو، سب سے پہلے ہم رینج کی تلاش کے اوپری اور کم حد تفویض:

Niz کی: = 1؛
سے verh: = H + 1؛

پھر سائیکل کو منظم "سب سے نیچے اوپری کی حد سے کم ہے جب تک":

Niz کی <سے verh جبکہ - 1 کروں
شروع

ہر قدم پر، ہم سیگمنٹ 2 تقسیم:

sredn: = (Niz کی + سے verh) div کے 2؛ {، تقریب div کے استعمال بقیہ بغیر تقسیم کی وجہ سے}

جائزہ لینے سے ہر وقت. درمیانے درجے کے مطلوبہ کیا جاتا ہے تو شے کے پاس پہلے سے ہی پایا گیا ہے کیونکہ، رکاوٹ سائیکل:

اگر sredn = ISK پھر توڑ؛

مطلوبہ زائد صف کے وسط عنصر، بائیں جانب ضائع کردے تو، یہ ہے کہ، اوسط کے اوپری حد عنصر مقرر:

اگر massiv [sredn]> ISK پھر سے verh: = sredn؛

اور اس کے برعکس پر، تو یہ کم حد ہوتا ہے:

ورنہ Niz کی: = sredn؛
آخر؛

یہ پروگرام میں ہو جائے گا کہ تمام ہے.

ہمیں یہ عملی طور پر بائنری کے طریقہ کار نظر آئے گا کہ کس طرح غور کرتے ہیں. اس صف پر غور کریں: 1، 3، 5، 7، 10، 12، 18 اور یہ تعداد 12 حاصل کرنے کی کوشش کرے گا.

کل میں ہم 7 عناصر ہے، لہذا چوتھی درمیانے، قدر 7 کرے گا.

سے زیادہ 12، 7، 1.3 اور 5 عناصر کے بعد سے، ہم کو ختم کر سکتے ہیں. پھر ہم 4 نمبر مل گیا ہے، 4/2 کوئی باقی 2. لہذا، ایک نیا عنصر 10 کی اوسط ہو جائے گا ہے.

چونکہ 12 10 سے زیادہ ہے، ہم ختم کر دینا 7. صرف 10، 12 اور 18 بنی ہوئی ہے.

یہاں، درمیانی عنصر کو پہلے ہی 12 ہے، یہ مطلوبہ تعداد ہے. یہ کام مکمل ہو گیا ہے - تعداد 12 نہیں ملا.