جستجوی دودویی در پایتون (Binary Search)

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

  1. لیست در پایتون
  2. If در پایتون
  3. الگوریتم بازگشتی

الگوریتم جستجوی دودویی در پایتون

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

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

جستجوی دودویی در پایتون

پیاده سازی جستجوی دودویی

حال نوبت پیاده سازی رسیده است. برای پیاده سازی جستجوی دودویی اول نیاز داریم که خانه های لیست ما sort باشد. ما فرض می‌کنیم که لیست ورودی خود مرتب است و نیاز به مرتب‌سازی ندارد (البته می‌توان لیست ورودی را مرتب‌سازی کرد)

بیشتر بخوانید:  الگوریتم فیلتر میانه در پایتون (Median Filter)

حال یک تابع مینویسیم که جست و جوی دودویی ما درون آن باشد. اسم تابع را binarySearch میگذاریم. کد این تابع به صورت زیر است:

بیشتر بخوانید:  حلقه while در پایتون (While Loop in python)

کد جستجوی دودویی به این صورت که ابتدا ما یک لیست تعریف می‌کنیم. سپس تابع جستجوی دودویی در پایتون را صدا میزنیم تا عدد 10 را پیدا کند. در صورتی که پیدا شد اندیس آن خانه را در لیست برمیگرداند و اگر نبود 1- برمیگرداند.

در تابع جستجوی دودویی در پایتون یک متغیر mid داریم که وسط لیست است. همانطوری که گفته شد ابتدا چک می‌کنیم که عددی به دنبال آن هستیم با خانه وسط یکی است یا خیر.

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

در غیر این صورت سمت راست به دنبال آن میرویم.

قبل از هر کاری هم یک بررسی کوچک میکنیم ببینیم خانه ای برای جست و جو باقی مانده است یا نه!!!!

خروجی کد بالا به صورت زیر می‌باشد:

Element is present at index  3

    پسورد فایل: www.codegate.ir

    دیدگاهتان را بنویسید

    نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *