مواد

• موازنہ چارٹ
• لکیری تلاش کی تعریف
• ثنائی تلاش کی تعریف
• نتیجہ اخذ کرنا

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

خطوطی تلاش اور بائنری تلاش کے درمیان اہم فرق یہ ہے کہ بائنری تلاش میں عناصر کی ترتیب شدہ فہرست سے کسی عنصر کی تلاش میں کم وقت لگتا ہے۔ تو یہ اندازہ لگایا گیا ہے کہ ثنائی تلاش کے طریقہ کار کی استعداد لکیری تلاش سے کہیں زیادہ ہے۔

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

1. موازنہ چارٹ
2. تعریف
3. کلیدی اختلافات
4. نتیجہ اخذ کرنا

موازنہ چارٹ

موازنہ کی بنیاد	لکیری تلاش	ثنائی تلاش
وقت کی پیچیدگی	O (N)	O (لاگ 2 ن)
بہترین معاملہ کا وقت	پہلا عنصر O (1)	سینٹر عنصر O (1)
کسی صف کے لئے ضروری ہے	ضرورت نہیں	سرنی ترتیب میں ہونی چاہئے
عناصر کی تعداد میں N کے لئے بدترین معاملہ	ن موازنہ کی ضرورت ہے	صرف لاگ کے بعد نتیجہ اخذ کیا جاسکتا ہے2ن موازنہ
پر عملدرآمد کیا جاسکتا ہے	صف اور لنکڈ فہرست	منسلک فہرست میں براہ راست لاگو نہیں کیا جاسکتا
آپریشن داخل کریں	آسانی سے فہرست کے آخر میں داخل کیا گیا	ترتیب شدہ فہرست کو برقرار رکھنے کے ل its اس کی مناسب جگہ پر کارروائی کرنے کی ضرورت ہے۔
الگورتھم کی قسم	فطرت میں Iterative	فطرت میں تقسیم اور فتح
افادیت	استعمال کرنے میں آسان اور کسی بھی حکم دینے والے عناصر کی ضرورت نہیں۔	بہرحال مشکل الگورتھم اور عناصر کو ترتیب سے ترتیب دیا جانا چاہئے۔
کوڈ کی لکیریں	کم	مزید

لکیری تلاش کی تعریف

خطی تلاش میں ، صف کے ہر عنصر کو ایک ایک کرکے ایک منطقی ترتیب سے بازیافت کیا جاتا ہے اور جانچ پڑتال کی جاتی ہے کہ آیا یہ مطلوبہ عنصر ہے یا نہیں۔ اگر تمام عناصر تک رسائی حاصل ہوجائے ، اور مطلوبہ عنصر نہ ملے تو تلاشی ناکام ہوگی۔ بدترین صورت میں ، اوسط کیس کی تعداد جس میں ہمیں صف (N / 2) کا نصف اسکین کرنا پڑسکتا ہے۔

لہذا لکیری تلاش کو اس تکنیک کی حیثیت سے تعبیر کیا جاسکتا ہے جو دیئے گئے شے کو تلاش کرنے کے لئے ترتیب وار سرے سے آگے بڑھ جاتی ہے۔ ذیل میں دیا گیا پروگرام سرچ کا استعمال کرتے ہوئے صف کے عنصر کی تلاش کو واضح کرتا ہے۔

کارکردگی لکیری تلاش کی

تلاش کے ٹیبل میں ریکارڈ تلاش کرنے میں وقت کی کھپت یا موازنہ کی تعداد تکنیک کی کارکردگی کا تعین کرتی ہے۔ اگر مطلوبہ ریکارڈ سرچ ٹیبل کی پہلی پوزیشن میں موجود ہے ، تو صرف ایک موازنہ کیا جائے گا۔ جب مطلوبہ ریکارڈ آخری ہے ، تو n موازنہ کرنا پڑے گا۔ اگر ریکارڈ تلاش کے ٹیبل میں کہیں پیش کرنا ہے تو ، اوسطا ، موازنہ کی تعداد ہوگی (n + 1/2) اس تکنیک کی بدترین کارکردگی کی کارکردگی O (n) ہے جس کا اطلاق پھانسی کے حکم سے ہوتا ہے۔

سی پروگرام لکیری تلاش کی تکنیک کے ساتھ کسی عنصر کی تلاش کرنا۔

# شامل کریں # شامل کریں باطل مین () {انٹ اے ، این ، آئی ، آئٹم ، لوک = -1؛ clrscr ()؛ f ("element n عنصر کی تعداد درج کریں:")؛ اسکینف ("٪ d"، & n)؛ f ("نمبر درج کریں: n")؛ (i = 0؛ i <= n-1؛ i ++) {اسکینف ("٪ d" ، اور ایک)؛ ؛ f (" n تلاش کرنے کے لئے نمبر درج کریں:")؛ اسکینف ("٪ d" ، اور آئٹم)؛ (i = 0؛ i <= n-1؛ i ++) {اگر (آئٹم == a) {لوک = i؛ توڑ }} اگر (لوک> = 0) {f (" n٪ d پوزیشن٪ d میں ملا ہے:" ، آئٹم ، لوک + 1)؛ } else {f (" n آئٹم موجود نہیں ہے")؛ ch گیچ ()؛ }

ثنائی تلاش کی تعریف

ثنائی کی تلاش ایک انتہائی موثر الگورتھم ہے۔ تلاش کی یہ تکنیک کم سے کم ممکن موازنہ میں دی گئی شے کو تلاش کرنے میں کم وقت خرچ کرتی ہے۔ بائنری تلاش کرنے کے ل first ، پہلے ، ہمیں سرنی عناصر کو ترتیب دینا ہوگا۔

اس تکنیک کے پیچھے منطق ذیل میں دی گئی ہے:

• پہلے ، صف کا درمیانی عنصر تلاش کریں۔
• صف کے درمیانی عنصر کا موازنہ اس کے عنصر سے کیا جاتا ہے جس کی تلاش کی جا.۔

تین معاملات پیدا ہوسکتے ہیں:

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

اسی مرحلے کو دہرائیں جب تک کہ کوئی عنصر تلاش نہ ہو یا تلاش کے علاقے میں ختم ہوجائے۔ اس الگورتھم میں ، ہر بار تلاش کے علاقے میں کمی آرہی ہے۔ لہذا موازنہ کی تعداد زیادہ سے زیادہ لاگ (N + 1) پر ہے۔ نتیجہ کے طور پر ، جب لکیری تلاش کے مقابلے میں یہ ایک موثر الگورتھم ہے ، لیکن بائنری تلاش کرنے سے پہلے صف کو ترتیب دینا ہوگا۔

سی پروگرام بائنری تلاش کی تکنیک کے ساتھ عنصر تلاش کرنے کے ل.

# شامل کریں باطل اہم () i انٹ i ، بھیک مانگنا ، آخر ، درمیانی ، ن ، تلاش ، صف؛ f ("عنصر کی تعداد درج کریں n")؛ اسکینف ("٪ d"، & n)؛ f ("٪ d نمبر درج کریں n"، n)؛ (i = 0؛ i <n؛ i ++) اسکینف ("٪ d" ، اور سرنی) کیلئے؛ f ("تلاش کرنے کے لئے نمبر درج کریں n")؛ اسکینف ("٪ d" ، اور تلاش)؛ بھیک = 0؛ آخر = n - 1؛ درمیانی = (بھیک + ختم) / 2؛ جبکہ (بھیک <= آخر) {اگر (سرنی <تلاش) بھیک = درمیانہ + 1؛ ورنہ اگر (سرنی == تلاش) {f ("تلاش کامیاب ہے۔ location n٪ d مقام٪ d پر ملا۔ n" ، تلاش ، وسط +1)؛ توڑ end دوسری آخر = درمیانی - 1؛ درمیانی = (بھیک + ختم) / 2؛ } اگر (بھیک مانگنا) f ("تلاش ناکام ہے!٪ d فہرست میں موجود نہیں ہے۔ n" ، تلاش کریں)؛ گیچ ()؛ }

1. خطوط کی تلاش فطرت میں تکراری ہے اور ترتیباتی نقطہ نظر کا استعمال کرتی ہے۔ دوسری طرف ، ثنائی کی تلاش تقسیم اور فتح کے نقطہ نظر کو نافذ کرتی ہے۔
2. خطوطی تلاش کی وقتی پیچیدگی O (N) ہے جبکہ بائنری تلاش میں O (لاگ) ہے₂ن)
3. خطوطی تلاش میں معاملات کا بہترین وقت پہلے عنصر یعنی O (1) کے لئے ہوتا ہے۔ اس کے برعکس ، بائنری تلاش میں ، یہ درمیانی عنصر ، یعنی ، O (1) کے لئے ہے۔
4. خطوطی تلاش میں ، عنصر کی تلاش کے لئے بدترین معاملہ تقابلی نمبر ہے۔ اس کے برعکس ، یہ لاگ ہے₂ثنائی تلاش کے لئے موازنہ کی نمبر
5. لکیری تلاش کو ایک صف میں اور منسلک فہرست میں بھی لاگو کیا جاسکتا ہے جبکہ بائنری تلاش کو براہ راست منسلک فہرست میں لاگو نہیں کیا جاسکتا ہے۔
6. جیسا کہ ہم جانتے ہیں کہ بائنری تلاش میں ترتیب شدہ صف کی ضرورت ہوتی ہے اسی وجہ سے اس کی ترتیب کی فہرست کو برقرار رکھنے کے ل its اس کی مناسب جگہ پر کارروائی کرنے کی ضرورت ہوتی ہے۔ اس کے برعکس خطوطی تلاش کو ترتیب دینے والے عناصر کی ضرورت نہیں ہوتی ہے ، لہذا فہرست کے آخر میں عنصر آسانی سے داخل ہوجاتے ہیں۔
7. لکیری تلاش کا استعمال آسان ہے ، اور کسی بھی آرڈرڈ عناصر کی ضرورت نہیں ہے۔ دوسری طرف ، بائنری سرچ الگورتھم تاہم مشکل ہے ، اور ضروری ہے کہ عناصر ترتیب میں ترتیب دیئے جائیں۔

نتیجہ اخذ کرنا

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

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