الگوریتم جستجوی باینری: عملکرد ، مزایا ، پیچیدگی زمان و فضا

Rohit Sharma مدیر برنامه برای برنامه های تجزیه و تحلیل داده های دیپلم PG-IIIT Bangalore ، PG است.

فهرست مطالب

مقدمه

در هر سیستم محاسباتی ، جستجو یکی از مهمترین ویژگی های توسعه است. تکنیک های جستجو در بازیابی فایل ، نمایه سازی و بسیاری از برنامه های دیگر استفاده می شود. تکنیک های جستجو زیادی در دسترس است. یکی از آنها تکنیک جستجوی باینری است.

دوره های علوم داده رایگان ما را بررسی کنید تا از رقابت استفاده کنید.

یک الگوریتم جستجوی باینری بر روی ایده غفلت از نیمی از لیست در هر تکرار کار می کند. این لیست را تا زمانی که مقداری را که به دنبال آن است در یک لیست معین پیدا کند ، در لیست قرار می دهد. یک الگوریتم جستجوی باینری یک به روزرسانی سریع به یک الگوریتم جستجوی خطی ساده است.

در این مقاله زمینه هایی مانند الگوریتم جستجوی باینری به طور متوسط پیچیدگی و جستجوی باینری بدتر به همراه ارائه ایده مختصر از الگوریتم جستجوی باینری ، به همراه پیچیدگی بهترین و بدتر الگوریتم جستجوی باینری ، مورد بحث قرار خواهد گرفت.

کار یک الگوریتم جستجوی باینری

اولین نکته ای که باید به آن توجه داشته باشید این است که یک الگوریتم جستجوی باینری همیشه در یک لیست مرتب شده کار می کند. از این رو اولین مرحله منطقی مرتب سازی لیست ارائه شده است. پس از مرتب سازی ، میانگین لیست با مقدار مورد نظر بررسی می شود.

• اگر مقدار مورد نظر برابر با ارزش شاخص مرکزی باشد ، این فهرست به عنوان پاسخ بازگردانده می شود.

• اگر مقدار هدف پایین تر از معامله فهرست مرکزی لیست باشد ، سمت راست لیست نادیده گرفته می شود.

• اگر مقدار مورد نظر از مقدار شاخص مرکزی بیشتر باشد ، نیمه چپ دور ریخته می شود.

• سپس این روند در لیست های کوتاه تکرار می شود تا مقدار هدف پیدا شود.

همچنین می توانید دوره Python Bootcamp ما را از ارتقاء تا حرفه خود در نظر بگیرید.

مثال شماره 1

بگذارید با یک مثال به الگوریتم نگاه کنیم. فرض کنید لیستی با شماره های زیر وجود دارد:

1 ، 15 ، 23 ، 7 ، 6 ، 14 ، 8 ، 3 ، 27

بگذارید مقدار مورد نظر را به عنوان 27 بدست آوریم. تعداد کل عناصر موجود در لیست 9 است.

اولین قدم برای مرتب کردن لیست است. پس از مرتب سازی ، لیست چیزی شبیه به این است:

1 ، 3 ، 6 ، 7 ، 8 ، 14 ، 15 ، 23 ، 27

از آنجا که تعداد عناصر موجود در لیست نه ، شاخص مرکزی در پنج نفر خواهد بود. مقدار در شاخص پنجم 8 است. مقدار مورد نظر ، 27 ، با مقدار 8 مقایسه می شود. ابتدا بررسی کنید که آیا مقدار برابر با 8 است یا خیر. اگر بله ، فهرست را برگردانید و از آن خارج شوید.

از آنجا که 27 از 8 بیشتر است ، ما قسمت چپ را نادیده می گیریم و فقط سمت راست لیست را می گذریم. لیست جدید برای Traverse:

توجه: در عمل ، لیست کوتاه نمی شود. فقط مشاهده باریک می شود. بنابراین ، "لیست جدید" نباید به عنوان تهیه لیست جدید یا کوتاه کردن نسخه اصلی اشتباه گرفته شود. اگرچه می توان آن را با یک لیست جدید اجرا کرد ، اما دو مشکل وجود دارد. اول ، یک حافظه سربار وجود خواهد داشت. هر لیست جدید پیچیدگی فضا را افزایش می دهد. و دوم ، شاخص های اصلی باید در هر تکرار ردیابی شوند.

شاخص مرکزی جدید بسته به اجرای آن می تواند به عنوان عنصر دوم یا سوم در نظر گرفته شود. در اینجا ، ما عنصر سوم را مرکزی در نظر خواهیم گرفت. مقدار 23 با مقدار 27 مقایسه می شود. از آنجا که مقدار بیشتر از مقدار مرکزی است ، ما نیمه چپ را دور می کنیم.

لیست برای Traverse:

از آنجا که این لیست فقط یک عنصر واحد را شامل می شود ، این عنصر اصلی در نظر گرفته می شود. از این رو ، ما مقدار مورد نظر را با 27 مقایسه می کنیم. همانطور که آنها مطابقت دارند ، مقدار شاخص 27 را در لیست اصلی برمی گردانیم.

مهارت های برتر علوم داده برای یادگیری در سال 2022

مثال شماره 2

در همان لیست ، بگذارید مقدار مورد نظر را 2 فرض کنیم.

اول ، مقدار مرکزی هشت با 2. مقایسه می شود. زیرا مقدار مورد نظر از مقدار مرکزی کوچکتر است ، ما تمرکز خود را به سمت چپ لیست محدود می کنیم.

گذرگاه جدید شامل موارد زیر خواهد بود:

بگذارید عنصر اصلی را به عنوان عنصر دوم بگیریم. مقدار مورد نظر دو با 3 مقایسه می شود. از آنجا که مقدار هنوز هم کوچکتر است ، ما دوباره تمرکز را به سمت چپ لیست محدود می کنیم.

گذرگاه جدید شامل موارد زیر خواهد بود:

از آنجا که لیست گذر تنها یک عنصر دارد ، مقدار مستقیماً با عنصر باقیمانده مقایسه می شود. می بینیم که مقادیر مطابقت ندارند. از این رو ، ما با یک پیام خطا از حلقه خارج می شویم: v alue یافت نشد.

وبینار علوم داده اختصاصی ارتقاء برای شما -

تحول و فرصت ها در تجزیه و تحلیل و بینش

پیچیدگی زمان و فضا

افراد غالباً از بدترین حالت و بهترین حالت درک باینری ندارند. پیچیدگی زمان الگوریتم جستجوی باینری O (log n) است. بهترین پیچیدگی زمان بهترین حالت o (1) خواهد بود که شاخص مرکزی مستقیماً با مقدار مورد نظر مطابقت داشته باشد. جستجوی باینری بدترین حالت با آن متفاوت است. بدترین حالت می تواند مقادیر موجود در هر دو لیست لیست یا مقادیر موجود در لیست باشد.

در حالت بدتر از پیچیدگی جستجوی باینری ، مقادیر به گونه ای وجود دارند که یا در انتهای لیست قرار دارند یا به هیچ وجه در لیست حضور ندارند. در زیر شرح مختصری از چگونگی یافتن پیچیدگی بدتر از جستجوی باینری آورده شده است.

معادله t (n) = t (n/2) +1 به عنوان رابطه عود برای جستجوی باینری شناخته می شود.

برای انجام تجزیه و تحلیل پیچیدگی زمان جستجوی باینری ، ما قضیه استاد را در معادله اعمال می کنیم و O (log n) را دریافت می کنیم.

پیچیدگی مورد بدتر از جستجوی باینری اغلب محاسبه ساده تر است اما اشکال بدبین بودن بیش از حد است.

از طرف دیگر ، نوع دیگری از تجزیه و تحلیل پیچیدگی زمان جستجوی باینری ، که الگوریتم جستجوی باینری به طور متوسط است ، یک اندازه گیری نادر است. از آنجا که محاسبه سخت تر است و به دانش عمیق در مورد میزان توزیع ورودی نیاز دارد ، افراد تمایل دارند از پیچیدگی متوسط الگوریتم جستجوی باینری جلوگیری کنند.

در زیر مراحل اساسی برای انجام جستجوی باینری وجود دارد.

1. عنصر میانی کل آرایه را پیدا کنید ، زیرا این کلید جستجو خواهد بود.
2. نگاه کنید که آیا کلید جستجو در وسط فاصله معادل مورد است یا خیر و یک شاخص از آن کلید جستجو را برگردانید.
3. اگر مقدار مورد میانی در فاصله بیشتر از کلید جستجو است ، نیمه پایین فاصله را کاهش دهید.
4. اگر برعکس ، نیمه بالا را پایین بیاورید.
5. از نقطه 2 تکرار کنید تا مقدار پیدا شود یا فاصله آن خالی شود.

همچنین ، برای کلیه برنامه های کارشناسی و کارشناسی ارشد ، به صفحه مشاوره مدرک ارتقاء مراجعه کنید.

دوره های علوم داده محبوب ما را کاوش کنید

پیچیدگی فضایی الگوریتم جستجوی باینری به اجرای الگوریتم بستگی دارد. دو روش برای اجرای آن وجود دارد:

1. روش تکراری
2. روش بازگشتی

هر دو روش کاملاً یکسان هستند، با دو تفاوت در اجرا. اول اینکه هیچ حلقه ای در روش بازگشتی وجود ندارد. دوم، به جای ارسال مقادیر جدید به تکرار بعدی حلقه، آنها را به بازگشت بعدی ارسال می کند. در روش تکراری، تکرارها را می توان از طریق شرایط حلقه کنترل کرد، در حالی که در روش بازگشتی، حداکثر و حداقل به عنوان شرط مرزی استفاده می شود.

در روش تکراری، پیچیدگی فضا O(1) خواهد بود. در حالی که در روش بازگشتی، پیچیدگی فضا O(log n) خواهد بود.

فواید

• الگوریتم جستجوی دودویی یک الگوریتم جستجوی نسبتاً ساده برای پیاده سازی است.

• این یک پیشرفت قابل توجه نسبت به جستجوی خطی است و در مقایسه با برخی از الگوریتم‌های جستجوی سخت‌تر، تقریباً یکسان عمل می‌کند.

• الگوریتم جستجوی دودویی، به جای بررسی متوالی لیست، در هر تکرار، فهرست را به نصف تقسیم می کند. در لیست های بزرگ، این روش می تواند واقعا مفید باشد.

مقالات محبوب علم داده ما را بخوانید

نتیجه

الگوریتم جستجوی دودویی یک الگوریتم پرکاربرد در حوزه محاسباتی است. این یک الگوریتم جستجوی چاق و دقیق است که می‌تواند روی مجموعه داده‌های بزرگ و کوچک به خوبی کار کند. الگوریتم جستجوی دودویی یک الگوریتم ساده و قابل اعتماد برای پیاده سازی است. با تجزیه و تحلیل زمان و مکان، مزایای استفاده از این تکنیک خاص مشهود است.

اگر کنجکاو هستید در مورد علم داده بیاموزید، دیپلم PG IIIT-B و upGrad در علم داده را بررسی کنید که برای حرفه ای ها ایجاد شده است و بیش از 10 مورد مطالعه و پروژه، کارگاه های عملی عملی، مشاوره با کارشناسان صنعت را ارائه می دهد. on-1 با مربیان صنعت، بیش از 400 ساعت یادگیری و کمک شغلی با شرکت های برتر.

آیا این درست است که جستجوی خطی برتر از جستجوی دودویی است؟

اگر فقط یک بار نیاز به جستجو داشته باشید، جستجوی خطی مطمئناً سریعتر از مرتب سازی و به دنبال آن جستجوی باینری خواهد بود اگر داده ها در اصل مرتب نشده باشند. از سوی دیگر، جستجوی باینری به عنوان روشی بسیار سریعتر از جستجوی خطی شناخته شده است. جستجوی باینری به شما امکان می دهد نیمی از موارد باقیمانده را در یک زمان حذف کنید، در حالی که جستجوی خطی از طریق هر عنصر یک به یک انجام می شود.

چه چیزی جستجوی درونیابی را از جستجوی دودویی متمایز می کند؟

جستجوی درون یابی یک روش جستجوی باینری مانند برای یافتن یک مقدار هدف مشخص در یک آرایه مرتب شده است. این شبیه به نحوه جستجوی افراد از طریق یک کتاب تلفنی برای یک نام خاص است ، با این که مقدار هدف برای مرتب سازی مطالب کتاب استفاده می شود. برای بررسی ، جستجوی باینری همیشه به عنصر مرکز سفر می کند. از طرف دیگر ، جستجوی درون یابی ممکن است بسته به ارزش کلید مورد نظر ، به مکان های مختلفی منجر شود. اگر مقدار کلید به عنصر نهایی نزدیک باشد ، به عنوان مثال ، جستجوی درون یابی در پایان بیشتر آغاز می شود.

آیا بهتر است یک جستجوی باینری بازگشتی یا یک جستجوی باینری تکراری انجام شود؟

نسخه بازگشتی جستجوی باینری دارای پیچیدگی فضایی O (log n) است ، اما نسخه تکراری دارای پیچیدگی فضایی O (log n) (1) است. در نتیجه ، در حالی که نسخه بازگشتی برای ساخت ساده است ، فرم تکراری کارآمدتر است.