>> [موسیقی بجانا]
>> ZAMYLA چان: آپ کو شاید پہلی بات تلاش کے بارے میں نوٹس ہے کہ ہم نے پہلے ہی
کوڈ ہمارے لئے لکھا ہے.
یہ تقسیم کوڈ کہا جاتا ہے.
تو ہم صرف ہمارے اپنے نہیں لکھ رہے ہیں اب شروع سے کوڈ.
بلکہ، ہم voids کو میں بھرنے کر رہے ہیں کچھ پہلے سے موجود کوڈ میں.
>> find.c پروگرام کے لئے اشارہ ٹیبل کو بھرنے کے لئے، تلاش
ایک صارف پیش انجکشن کے لئے ٹیبل، اور اس طرح بلا اور کی طرف سے اس کرتا ہے
تلاش، افعال کی وضاحت helpers.c میں.
تو find.c پہلے ہی لکھا ہے.
آپ کا کام مددگار لکھنے کے لئے ہے.
>> تو ہم کیا کر رہے ہیں؟
ہم دو افعال عملدرآمد کر رہے ہیں.
صحیح واپس جس میں تلاش کریں، تو ایک قیمت واپس لوٹنے، ٹیبل میں پایا جاتا ہے
جھوٹی قیمت ہے نہیں ٹیبل میں.
اور پھر ہم بھی طرح عملدرآمد کر رہے ہیں جس کی اقدار سے ملاقات کی طرح صف.
>> تو تلاش نمٹنے ہیں.
تلاش فی الحال ایک کے طور پر لاگو کیا جاتا ہے لکیری تلاش، لیکن آپ کو زیادہ سے زیادہ کر سکتے ہیں
اس سے بہتر.
لکیری تلاش O میں لاگو کیا جاتا ہے (ن) کے وقت کی، جس میں کافی سست ہے.
اگرچہ، یہ تلاش کر سکتے ہیں اس کو دی گئی کسی بھی فہرست.
آپ کا کام بائنری تلاش کو لاگو کرنے کے لئے ہے، لاگ ان ن کے وقت اے ختم ہو گیا ہے جس میں.
یہ بہت تیز ہے.
>> لیکن ایک شرط ہے.
بائنری تلاش صرف تلاش کر سکتے ہیں پہلے کے مطابق فہرستوں کے ذریعے.
ایسا کیوں ہے؟
>> چلو ایک مثال کے طور پر نظر آتے ہیں.
اقدار کی ایک صف کو دیکھتے ہوئے، ٹیبل، ہم تلاش کر جا رہے ہیں
ایک انجکشن کے لئے.
اور اس مثال میں، عددی تین.
بائنری تلاش پر کام کرتا ہے اس طرح ہے کہ ہم مشرق کی قیمت کا موازنہ
زیادہ کی طرح انجکشن صف، کس طرح ہم مشرق کے لئے ایک فون کتاب کھولی
ہفتے صفر میں صفحہ.
>> تو مشرق کی قیمت کا موازنہ کے بعد انجکشن، آپ کو یا تو ضائع کر سکتے ہیں
بائیں یا صف کے دائیں نصف آپ حد سخت کی طرف سے.
اس صورت میں، تین کے بعد سے، ہمارے انجکشن، 10 سے بھی کم، درمیانی قیمت، ہے
حق پابند کم کر سکتے ہیں.
لیکن آپ کی حد کرنے کی کوشش کریں ہر ممکن حد تک تنگ.
مشرق قیمت انجکشن نہیں ہے تو، تو آپ کو آپ کی ضرورت نہیں ہے
آپ کی تلاش میں شامل ہو.
تو آپ کو حق پابند کر رہے ہیں سخت کر سکتا ہے صرف ایک چھوٹے سے تھوڑا سا زیادہ تلاش کی حد،
اور تو اور تو آگے تک آپ کو آپ کے انجکشن تلاش.
>> تو کیا pseudocode طرح لگتی ہے؟
ہم اب بھی کے ذریعے تلاش کر رہے ہیں ٹھیک ہے جبکہ کی فہرست اور بھی عناصر ہیں
میں نظر آتے ہیں، ہم، فہرست کے وسط لے اور ہے کہ مشرق کی قیمت کا موازنہ
ہمارے انجکشن.
اگر وہ برابر ہیں، تو یہ ہم نے کا مطلب انجکشن پایا اور ہم کر سکتے ہیں
سچ واپس.
>> دوسری صورت میں، انجکشن سے کم ہے تو مشرق کی قیمت، اس کے بعد کہ ہم مطلب
صحیح نصف ضائع، اور صرف کر سکتے ہیں صف کے بائیں جانب تلاش.
دوسری صورت میں، ہم تلاش کر لیں گے صف کے دائیں جانب.
اور آخر میں، اگر آپ کو کسی بھی ضرورت نہیں ہے مزید تلاش کرنے کے لئے چھوڑ دیا عناصر لیکن آپ
اگر آپ نے ابھی تک اپنی انجکشن نہیں مل سکا ہے جھوٹے واپس کیونکہ انجکشن
یقینی طور پر ٹیبل میں نہیں ہے.
>> اس pseudocode کے بارے میں اب ایک صاف بات بائنری تلاش میں یہ ہو سکتا ہے
تکراری یا تو کے طور پر تشریح یا پنراورتی عمل.
آپ کو بلایا تو اس پنراورتی ہو گا تلاش کے اندر اندر تلاش تقریب
صف کے یا تو نصف پر کام.
ہم تھوڑا بعد میں تکرار کا احاطہ کریں گے کورس کے، لیکن یہ ایک ہے کہ جانتے ہیں
آپشن آپ کو کرنے کی کوشش کرنا چاہتے ہیں.
>> اب ترتیب کو دیکھو.
ترتیب ایک صف اور عددی لیتا ہے صف کے سائز ہے جو ن،.
اب مختلف مختلف اقسام ہیں قسم کے، اور آپ کو کچھ میں دیکھ سکتے ہیں
ڈیمو اور وضاحت کے لئے شارٹس.
کے لئے واپسی کی قسم ہماری ترتیب تقریب باطل ہے.
تو ہے کہ ہم نہیں جا رہے ہیں کا مطلب ہے کہ ترتیب کی طرف سے کسی بھی صف واپس کرنے کے لئے.
ہم اصل میں بہت تبدیل کرنے کے لئے جا رہے ہیں ہم میں منظور کیا گیا تھا اس صف.
>> arrays کے ہیں کیونکہ اور یہ کہ ممکن ہے اب ہم سی میں حوالہ کی طرف سے منظور کریں گے
بعد میں اس بارے میں مزید دیکھیں، لیکن انتقال کے درمیان بنیادی فرق
ایک عدد صحیح اور پاسنگ کی طرح کچھ میں ایک صف میں، یہ ہے کہ جب آپ
ایک عدد صحیح میں منتقل، سی صرف کی جا رہی ہے اس عددی کی ایک کاپی بنانے کے لئے اور منتقل
تقریب کے لئے اس.
اصل متغیر کو تبدیل نہیں کیا جائے گا تقریب ختم ہو گیا ہے ایک بار.
ایک صف کے ساتھ، دوسری طرف، یہ ہے ایک کاپی بنانے کے لئے جا، اور آپ کو دونگا
ایڈیٹنگ ہو بہت صف خود.
>> تو ترتیب کی ایک قسم ہے انتخاب کی طرح.
انتخاب کی طرح میں شروع ہونے والے کی طرف سے کام کرتا ہے آپ iterate کے پھر شروع، اور
سے زیادہ اور سب سے چھوٹی عنصر کو تلاش کریں.
اور پھر آپ کا تبادلہ ہے کہ سب سے چھوٹی سب سے پہلے ایک کے ساتھ عنصر.
اور پھر آپ دوسرے عنصر پر منتقل ، اگلے سب سے چھوٹی تلاش
تو عنصر، اور سویپ کے ساتھ صف میں دوسرے عنصر کی وجہ سے
پہلا عنصر پہلے ہی کے مطابق ہے.
اور تو آپ کو ہر کے لئے جاری سب سے چھوٹی شناخت میں عنصر
قیمت اور اسے باہر گماگمن.
>> 0، بہت پہلے عنصر کے برابر کے لئے ن مائنس 1 کے لئے، آپ کا آپس میں موازنہ کرنے کے لئے جا رہے ہیں
ہر اگلے اس کے بعد قیمت اور تلاش کم از کم قیمت کے انڈیکس.
آپ کو کم از کم قیمت انڈیکس ایک بار جب، آپ صف کی اس قدر تبادلہ کر سکتے ہیں
کم از کم اور صف میں
>> ترتیب کی ایک اور قسم ہے کہ آپ کر سکتے ہیں کو لاگو بلبلا طرح ہے.
فہرست پر تو بلبلا طرح iterates ہے ملحق عناصر اور موازنہ
عناصر گماگمن کہ غلط حکم میں ہیں.
اور اس طرح، سب سے بڑا عنصر بلبلا ختم کرنے کے لئے کرے گا.
اور فہرست میں ایک بار نہیں کے مطابق ہے عناصر میں تبدیل کر دیا گیا ہے.
>> لہذا ان کی طرح دو مثالیں ہیں آپ کے لئے پر عملدرآمد کر سکتے ہیں کہ یلگوردمز
تلاش کے پروگرام.
آپ کی طرح ختم، اور آپ کو ایک بار تلاش کیا، آپ فارغ ہو.
میرا نام کیا Zamyla ہے، اور اس CS50 ہے.
>> [موسیقی بجانا]