[موسیقی بجانے] 

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

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

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

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

آپ کے لئے تلاش کر رہے ہیں قیمت ہے تو صف کے اس عنصر میں، کو روکنے کے. تم نے یہ محسوس. یہ بہت اچھا ہے. دوسری صورت میں، ہدف ہے درمیان میں کیا ہے کے مقابلے میں کم، تو قیمت تو ہم تلاش کر رہے ہیں کے لئے، جو ہم دیکھتے ہیں کے مقابلے میں کم ہے پھر اس عمل کو دہرائیں، لیکن بجائے، آخر نقطہ تبدیل اصل ہونے کی وجہ سے مکمل صف مکمل، صرف بائیں کرنے کے لئے ہو جہاں ہم صرف دیکھا. 

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

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

تو ہم شروع کر سکتے ہیں؟ ٹھیک ہے، بالکل. میں نے کہا کیا یاد بائنری تلاش کے بارے میں؟ ہم نے ایک پر ایسا نہیں کر سکتے ہیں اور ناچھانٹا ہوا سرنی یا، ہم اس کی ضمانت نہیں کر رہے ہیں بعض عناصر یا اقدار نہیں ہیں اتفاقی طور پر کیا جا رہا ہے ضائع جب ہم صرف صف کے نصف کو نظر انداز کرنے کا فیصلہ. 

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

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

تو ہم نکتہ کی طرف سے حساب 0 علاوہ 2 سے تقسیم 14 انہوں نے مزید کہا؛ خوبصورت براہ راست مڈ پوائنٹ. اور ہم کہہ سکتے ہیں کہ مڈ پوائنٹ اب 7. تو 15 ہم کے لئے تلاش کر رہے ہیں کیا ہے؟ نہیں ایسا نہیں. ہم 19 کے لئے تلاش کر رہے ہیں. لیکن ہم 19 زیادہ جانتے ہیں کہ ہم مشرق میں پایا ہے کے مقابلے میں. 

تو ہم کیا کر سکتے ہیں ہے نقطہ آغاز تبدیل صرف کے دائیں جانب ہونا مڈ پوائنٹ، اور پھر عمل کو دہرائیں. ہم ایسا اور جب، اب ہم کا کہنا ہے کہ نیا نقطہ آغاز سرنی مقام 8. کیا ہم مؤثر طریقے سے کیا ہے ہے 15 کے بائیں نظر انداز کر دیا سب کچھ. ہم آدھے کا خاتمہ ہے مسئلے کی، اور اب، بجائے تلاش کرنے کے ہمارے صف میں 15 سے زائد عناصر، ہم صرف 7 تلاش کرنے کے لئے ہے. تو 8 نئے نقطہ آغاز ہے. 14 اب بھی آخر نقطہ ہے. 

اور اب، ہم ایک بار پھر اس سے زیادہ جانا. ہم نئی مڈ پوائنٹ کا حساب. 8 کے علاوہ 14 2 11 کی طرف سے تقسیم، 22. ہم اس کے لئے تلاش کر رہے ہیں کیا ہے؟ نہیں ایسا نہیں. ہم ہے کہ ایک قیمت کے لئے تلاش کر رہے ہیں ہم صرف مل گیا ہے کے مقابلے میں کم. تو ہم دہرانے کے لئے جا رہے ہیں دوبارہ عمل. ہم آخر نقطہ کو تبدیل کرنے جا رہے ہیں صرف مڈ پوائنٹ کے بائیں کرنے کے لئے ہو. تو نئے آخر نقطہ 10 بن جاتا ہے. اور اب، اس کا صرف ایک حصہ ہے سرنی ہم کے ذریعے حل کرنے کی ہے. تو کیا اب ہم ختم کر دیا ہے 15 عناصر کے 12. ہم جانتے ہیں کہ اگر 19 سرنی میں موجود ہے، اس عنصر کے درمیان کہیں موجود ہونا ضروری ہے 8 نمبر اور عنصر نمبر 10. 

تو ہم ایک بار پھر نئے مڈ پوائنٹ کا حساب. 8 کے علاوہ 10 2 9 کی طرف سے تقسیم، 18. اور اس معاملے میں، دیکھو، ہدف مشرق میں ہے. ہم کے لئے تلاش کر رہے ہیں بالکل وہی جو. ہم کو روک سکتے ہیں. ہم نے کامیابی سے مکمل ایک بائنری تلاش. بالکل ٹھیک. تو ہم اس الگورتھم جانتے ہدف ہے تو کام کرتا ہے کہیں صف کے اندر. اس الگورتھم کام تو کرتا ہے ہدف صف میں نہیں ہے؟ ٹھیک ہے، یہ شروع کر دیں ایک بار پھر، اور اس وقت، کی عنصر کے لئے دیکھو ضعف ہم دیکھ سکتے ہیں جس میں 16، صف میں کہیں بھی موجود نہیں ہے. 

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

تو قدم پہلے کیا ہے؟ مڈ پوائنٹ کا حساب لگائیں موجودہ صف کی. نکتہ کیا ہے موجودہ صف کی؟ ویسے، یہ درست، 7 ہے؟ 2 سے تقسیم 14 پلس 0 7. ہم کے لئے تلاش کر رہے ہیں 15 ہے؟ نہیں. یہ بہت قریب ہے، لیکن ہم دیکھ رہے ہیں اس سے تھوڑا بڑا ایک قیمت کے لئے. 

تو ہم اس کے لئے جا رہا ہے جانتے ہیں کہ 15 کے بائیں کہیں ہو. ہدف سے زیادہ ہے کیا مڈ پوائنٹ میں ہے. اور اس طرح ہم نئے نقطہ آغاز کے لئے مقرر صرف مشرق کے حق میں ہو. مڈ پوائنٹ تو، اس وقت 7 کے نئے نقطہ آغاز 8 کا کہنا ہے کہ دو. اور ہم مؤثر طریقے سے کیا ہے پھر سے کیا نظر انداز کر دیا جاتا ہے صف کی پوری بائیں نصف. 

اب، ہم دہرانے ایک بار پر عملدرآمد. نئے مڈ پوائنٹ کا حساب لگائیں. 8 کے علاوہ 14 2 11 کی طرف سے تقسیم، 22. ہم کے لئے تلاش کر رہے ہیں 23؟ بدقسمتی سے، کوئی. ہم نے ایک قیمت کے لئے تلاش کر رہے ہیں اس سے بھی کم 23 ہے. اور تو اس صورت میں، ہم جا رہے ہیں آخر نقطہ کو تبدیل کرنے کے لئے صرف ہونا موجودہ midpoint کے بائیں. موجودہ midpoint 11 ہے، اور تو ہم نئے آخر نقطہ قائم کریں گے ہمیں جانا اگلی بار کے لئے 10 اس عمل کے ذریعے. 

ایک بار پھر، ہم ایک بار پھر عمل کے ذریعے جانا. مڈ پوائنٹ کا حساب لگائیں. 2 سے تقسیم 8 کے علاوہ 10 9. ہم کے لئے تلاش کر رہے ہیں 19؟ بدقسمتی سے، کوئی. ہمیں اب تک تلاش کر رہے ہیں اس سے بھی کم ایک بڑی تعداد. تو ہم آخر نقطہ اس وقت تبدیل کر دیں گے صرف مڈ پوائنٹ کے بائیں کرنے کے لئے ہو. مڈ پوائنٹ، اس وقت 9 تو آخر نقطہ 8 ہو جائے گا. اور اب، ہم صرف دیکھ رہے ہیں ایک عنصر سرنی میں. 

اس صف کی midpoint کیا ہے؟ ٹھیک ہے، یہ، 8 سے شروع ہوتی ہے 8 پر ختم ہوتا ہے، مڈ پوائنٹ 8. کہ ہم کے لئے تلاش کر رہے ہیں کیا ہے؟ ہم 17 کے لئے تلاش کر رہے ہیں؟ نہیں، ہم 16 کے لئے تلاش کر رہے ہیں. اس صف میں موجود تو، یہ کہیں موجود ہونا ضروری ہے ہم اس وقت کہاں ہیں کے بائیں. تو کیا ہم کیا کرنے جا رہے ہیں؟ ٹھیک ہے، ہم صرف ہو آخر نقطہ قائم کریں گے موجودہ midpoint کے بائیں. تو ہم 7 آخر نقطہ کو تبدیل کر دونگا. آپ صرف کیا دیکھتے ہو اگرچہ، یہاں کیا ہوا؟ اب یہاں دیکھو. 

شروع کریں اب آخر سے زیادہ ہے. مؤثر طریقے سے، دونوں سروں ہمارے صف کے تجاوز کر دی ہے، اور شروع نقطہ ہے اب آخر نقطہ کے بعد. ٹھیک ہے، یہ نہیں ہے صحیح، کوئی مطلب؟ تو اب، کیا ہم کہہ سکتے ہیں ہم ہے 0 سائز کے ایک ذیلی سرنی ہے. اور ایک بار ہم ہو رہے ہیں اس نقطہ، اب ہم کر سکتے ہیں اس عنصر کی ضمانت 16 صف میں کوئی وجود نہیں ہے، نقطہ آغاز کی وجہ سے اور آخر نقطہ سے تجاوز کر دی. اور اس طرح یہ وہاں نہیں ہے. اب، یہ تھوڑا سا ہے کہ محسوس نقطہ آغاز اور اختتام کے مقابلے میں مختلف ایک ہی ہونے کی طرف اشارہ. ہم تلاش کر رہا تھا تو 17، ہوگا صف، اور نقطہ آغاز میں کیا گیا کہ گزشتہ iteration کے اور آخر نقطہ ان پوائنٹس کو پار کرنے سے پہلے، ہم وہاں 17 پاتے. وہ ہم کر سکتے ہیں کہ کراس جب یہ صرف ہے عنصر نہیں ہے کہ اس بات کی ضمانت صف میں موجود ہیں. 

تو اس کی ایک بہت کم لے لکیری تلاش سے اقدامات. بدترین حالات میں، ہم نے ن عناصر کی ایک فہرست کو تقسیم کرنے کے بار بار نصف میں، ہدف تلاش کرنے کے لئے یا تو اس وجہ ہدف عنصر آخری میں کہیں ہو جائے گا ڈویژن، یا یہ بالکل کوئی وجود نہیں ہے. بدترین صورت میں، ہم کرنا پڑے تم جانتے ہو صف تقسیم؟ (ن) کے اوقات کے لاگ ان؛ ہم مسئلہ کاٹ کرنا پڑے اوقات میں سے نصف ایک مخصوص تعداد میں. اوقات میں یہ تعداد لاگ ان ن ہے. 

بہترین دوسری صورت کیا ہے؟ ویسے، پہلی بار ہم نے مڈ پوائنٹ کا حساب، ہم کے لئے تلاش کر رہے ہیں کو تلاش. تمام گزشتہ میں بائنری تلاش پر مثالیں ہم نے تو ہم صرف، ختم ہو گیا ہے عنصر 15 لئے تلاش کیا گیا، ہم کہ فوری طور پر پایا جائے گا. یہ بہت شروع میں تھا. اس کی midpoint تھا ایک تقسیم میں پہلی کوشش بائنری تلاش میں ایک ڈویژن. 

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

میں ڈوگ لایڈ ہوں. یہ کاوچ سرفنگ کے 50 ہے.