در این قسمت تیم کدگیت را با آموزش جستجوی دودویی در پایتون همراهی کنید. در این جلسه یکی از الگوریتمهای قدیمی جستجو یعنی جستجوی دودویی را معرفی می کنیم. ابتدا نحوه کار الگوریتم جستجوی دودویی را توضیح داده سپس به پیاده سازی آن در زبان برنامه نویسی پایتون خواهیم پرداخت. پیشنهاد میکنیم پیش نیاز های این آموزش را مطالعه کنید:
- لیست در پایتون
- If در پایتون
- الگوریتم بازگشتی
ویدئو آموزش بخش اول
الگوریتم جستجوی دودویی در پایتون
الگوریتم جستجوی دودویی تکنیکی است برای یافتن یک مقدار عددی از میان مجموعهای از اعداد مرتب. این متد محدوده جستجو را در هر مرحله به نصف کاهش میدهد، بنابراین هدف مورد نظر یا به زودی پیدا میشود و یا مشخص میشود که مقدار مورد جستجو در فهرست وجود ندارد.
جستجوی دودویی فقط در آرایه های مرتب استفاده می شود.در این روش عنصر مورد نظر با خانه وسط آرایه مقایسه می شود اگر با این خانه برابر بود جستجو تمام می شود اگر عنصر مورد جستجو از خانه وسط بزرگتر بود جستجو در بخش بالایی آرایه و در غیر این صورت جستجو در بخش پایینی آرایه انجام می شود(فرض کرده ایم آرایه به صورت صعودی مرتب شده است) این رویه تا یافتن عنصر مورد نظر یا بررسی کل خانه های آرایه ادامه می یابد.
پیاده سازی جستجوی دودویی
حال نوبت پیاده سازی است. برای پیاده سازی جستجوی دودویی اول نیاز داریم که خانه های لیست ما sort باشد. ما فرض میکنیم که لیست ورودی خود مرتب است و نیاز به مرتبسازی ندارد (البته میتوان لیست ورودی را مرتبسازی کرد)
حال یک تابع مینویسیم که جست و جوی دودویی ما درون آن باشد. اسم تابع را binarySearch میگذاریم. کد این تابع به صورت زیر است:
def binarySearch (arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
if __name__ == '__main__':
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Function call
result = binarySearch(arr, 00, len(arr)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in array")
کد جستجوی دودویی به این صورت که ابتدا ما یک لیست تعریف میکنیم. سپس تابع جستجوی دودویی در پایتون را صدا میزنیم تا عدد 10 را پیدا کند. در صورتی که پیدا شد اندیس آن خانه را در لیست برمیگرداند و اگر نبود 1- برمیگرداند.
در تابع جستجوی دودویی در پایتون یک متغیر mid داریم که وسط لیست است. همانطوری که گفتیم ابتدا چک میکنیم که عددی به دنبال آن هستیم با خانه وسط یکی است یا خیر.
if arr[mid] == x:
return mid
اگر حالت بالا اتفاق نیفتاد باید به جست و جو ادامه بدهیم. اگر عددی که به دنبال آن هستیم کوچکتر از خانه وسط بود سمت چپ لیست را جست و جو میکنیم.
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
در غیر این صورت سمت راست به دنبال آن میرویم.
else:
return binarySearch(arr, mid + 1, r, x)
قبل از هر کاری هم یک بررسی کوچک میکنیم ببینیم خانه ای برای جست و جو باقی مانده است یا نه!!!!
if r >= l:
خروجی کد بالا به صورت زیر میباشد:
Element is present at index 3
