از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
جستجوی باینری در پایتون
سرفصلهای مطلب
معرفی
جستجوی باینری یک الگوریتم جستجوی کارآمد است که کار می کند روی آرایه های مرتب شده اغلب به عنوان یکی از اولین نمونه های الگوریتم هایی که در زمان لگاریتمی اجرا می شوند استفاده می شود (O(logn)) به دلیل رفتار شهودی آن و یک الگوریتم اساسی در علوم کامپیوتر است.
در این مقاله، ما به ایده پشت و اجرای پایتون خواهیم پرداخت جستجوی باینری.
جستجوی باینری – مثال
جستجوی باینری کار می کند روی آ تفرقه بینداز و حکومت کن رویکرد و تکیه دارد روی این واقعیت که آرایه مرتب شده است برای حذف نیمی از نامزدهای احتمالی در هر تکرار. به طور خاص، عنصر میانی آرایه مرتب شده را با عنصری که در جستجوی آن است مقایسه می کند تا تصمیم بگیرد کجا به جستجو ادامه دهد.
اگر عنصر هدف بزرگتر از عنصر میانی باشد – نمی توان آن را در نیمه اول مجموعه قرار داد، بنابراین دور انداخته می شود. همین امر برعکس است.
توجه داشته باشید: اگر آرایه دارای تعدادی عنصر زوج باشد، برای شروع از کدام یک از دو عنصر “وسط” استفاده می کنیم.
قبل از اینکه به توضیح چگونگی کارکرد جستجوی باینری ادامه دهیم، اجازه دهید به یک مثال سریع نگاه کنیم:
همانطور که می بینیم، ما با اطمینان می دانیم که از آنجایی که آرایه مرتب شده است، عنصر مورد نظر ما (18
) در نیمه اول آرایه اصلی نیست.
توجه داشته باشید: از حالا روی، عنصر مورد نظر را به عنوان علامت گذاری می کنیم x
.
وقتی می دانیم که در کدام نیمی از آرایه اصلی قرار دارد x
است، ما می توانیم این را دقیقا تکرار کنیم process با آن نیمه و دوباره آن را به دو نیم تقسیم کنید، نیمه ای که مطمئناً حاوی آن نیست را دور بریزید x
:
این را تکرار می کنیم process تا زمانی که به یک زیرآرایه که فقط یک عنصر را شامل می شود، می رسیم. بررسی می کنیم که آیا آن عنصر وجود دارد یا خیر x
. اگر چنین است – ما پیدا کردیم x
، اگر اینطور نیست – x
اصلا در آرایه وجود ندارد.
اگر به این موضوع دقت کنید، می توانید متوجه شوید که در بدترین حالت (x
در آرایه وجود ندارد)، ما باید تعداد بسیار کمتری از عناصر را نسبت به یک آرایه مرتب نشده بررسی کنیم – که به چیزی بیشتر در طول خطوط نیاز دارد. جستجوی خطی، که به طرز دیوانه کننده ای ناکارآمد است.
برای دقیق تر، تعداد عناصری که باید در بدترین حالت بررسی کنیم، است O(log2ن) جایی که ن تعداد عناصر آرایه است.
هر چه آرایه بزرگتر باشد، تأثیر بیشتری می گذارد:
اگر آرایه ما 10 عنصر داشت، برای یافتن هر کدام باید فقط 3 عنصر را بررسی کنیم
x
یا نتیجه بگیرید که آنجا نیست. یعنی 33.3 درصد.با این حال، اگر آرایه ما 10،000،000 عنصر داشت، فقط باید 24 عنصر را بررسی کنیم. این 0.0002٪ است.
پیاده سازی جستجوی باینری
جستجوی باینری یک است الگوریتم بازگشتی طبیعی از همان زمان process تکرار می شود روی آرایه های کوچکتر و کوچکتر تا زمانی که آرایه ای به اندازه 1 پیدا شود. با این حال، البته یک اجرای تکراری نیز وجود دارد، و ما هر دو رویکرد را نشان خواهیم داد.
بازگشتی
بیایید با پیاده سازی بازگشتی شروع کنیم زیرا طبیعی تر است:
def binary_search_recursive(array, element, start, end):
if start > end:
return -1
mid = (start + end) // 2
if element == array(mid):
return mid
if element < array(mid):
return binary_search_recursive(array, element, start, mid-1)
else:
return binary_search_recursive(array, element, mid+1, end)
توجه داشته باشید: این کد برای نشان دادن بهترین استفاده از serach باینری ساده شده است. این به طور کامل آماده تولید نیست، زیرا فاقد مدیریت صحیح خطا است. با این وجود، میتوانید از آن برای اجرای جستجوی باینری استفاده کنید، فقط توجه داشته باشید که نمیتوانید پیامهای خطای مناسبی را دریافت کنید.
بیایید نگاهی دقیق تر به این کد بیندازیم. اگر از بازگشت خارج می شویم start
عنصر بالاتر از end
عنصر:
if start > end:
return -1
این به این دلیل است که این وضعیت تنها زمانی رخ می دهد که عنصر در آرایه وجود نداشته باشد. اتفاقی که می افتد این است که در زیر آرایه فعلی فقط یک عنصر داریم و آن عنصر با عنصر مورد نظر ما مطابقت ندارد.
در این مرحله، start
برابر است با end
. با این حال، از آنجایی که element
برابر نیست array(mid)
، دوباره آرایه را به گونه ای “تقسیم” می کنیم که یا کاهش می دهیم end
1 یا افزایش دهید start
توسط یک، و بازگشت وجود دارد روی آن شرط
ما می توانستیم این کار را با استفاده از یک رویکرد متفاوت انجام دهیم:
if len(array) == 1:
if element == array(mid):
return mid
else:
return -1
بقیه کد منطق “بررسی عنصر میانی، ادامه جستجو در نیمه مناسب آرایه” را انجام می دهد. شاخص عنصر میانی را پیدا می کنیم و بررسی می کنیم که آیا عنصر مورد جستجو با آن مطابقت دارد یا خیر:
mid = (start + end) // 2
if elem == array(mid):
return mid
اگر اینطور نیست، بررسی می کنیم که آیا عنصر کوچکتر یا بزرگتر از عنصر میانی است:
if element < array(mid):
return binary_search_recursive(array, element, start, mid-1)
else:
return binary_search_recursive(array, element, mid+1, end)
بیایید ادامه دهیم و این الگوریتم را با کمی تغییر اجرا کنیم تا نشان دهد کدام زیرآرایه کار می کند روی در حال حاضر:
element = 18
array = (1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29)
print("Searching for {}".format(element))
print("Index of {}: {}".format(element, binary_search_recursive(array, element, 0, len(array))))
اجرای این کد منجر به موارد زیر می شود:
Searching for 18
Subarray in step 0:(1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29)
Subarray in step 1:(16, 18, 24, 28, 29)
Subarray in step 2:(16, 18)
Subarray in step 3:(18)
Index of 18: 7
واضح است که چگونه فضای جستجو را در هر تکرار به نصف کاهش می دهد و به عنصر مورد نظر ما نزدیک و نزدیکتر می شود. اگر بخواهیم عنصری را جستجو کنیم که در آرایه وجود ندارد، خروجی این خواهد بود:
Searching for 20
Subarray in step 0: (4, 14, 16, 17, 19, 21, 24, 28, 30, 35, 36, 38, 39, 40, 41, 43)
Subarray in step 1: (4, 14, 16, 17, 19, 21, 24, 28)
Subarray in step 2: (19, 21, 24, 28)
Subarray in step 3: (19)
Index of 20: -1
و فقط برای سرگرمی، میتوانیم چند آرایه بزرگ را جستجو کنیم و ببینیم که جستجوی باینری چند مرحله طول میکشد تا بفهمیم آیا یک عدد وجود دارد یا خیر:
Searching for 421, in an array with 200 elements
Search finished in 6 steps. Index of 421: 169
Searching for 1800, in an array with 1500 elements
Search finished in 11 steps. Index of 1800: -1
Searching for 3101, in an array with 3000 elements
Search finished in 8 steps. Index of 3101: 1551
تکراری
رویکرد تکراری بسیار ساده و شبیه به رویکرد بازگشتی است. در اینجا، ما فقط بررسی ها را در a انجام می دهیم while
حلقه:
def binary_search_iterative(array, element):
mid = 0
start = 0
end = len(array)
step = 0
while (start <= end):
print("Subarray in step {}: {}".format(step, str(array(start:end+1))))
step = step+1
mid = (start + end) // 2
if element == array(mid):
return mid
if element < array(mid):
end = mid - 1
else:
start = mid + 1
return -1
بیایید یک آرایه را پر کنیم و عنصری را در آن جستجو کنیم:
element = 18
array = (1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29)
print("Searching for {} in {}".format(element, array))
print("Index of {}: {}".format(element, binary_search_iterative(array, element)))
اجرای این کد خروجی زیر را به ما می دهد:
Searching for 18 in (1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29)
Subarray in step 0: (1, 2, 5, 7, 13, 15, 16, 18, 24, 28, 29)
Subarray in step 1: (16, 18, 24, 28, 29)
Subarray in step 2: (16, 18)
Subarray in step 3: (18)
Index of 18: 7
نتیجه
جستجوی باینری یک الگوریتم باورنکردنی برای استفاده است روی آرایه های بزرگ و مرتب شده یا هر زمان که قصد داریم عناصر را به طور مکرر در یک آرایه جستجو کنیم.
هزینه مرتب سازی آرایه یک بار و سپس استفاده از جستجوی باینری برای یافتن چندین بار عناصر در آن به مراتب بهتر از جستجوی خطی است. روی یک آرایه مرتب نشده فقط برای اینکه بتوانیم از هزینه مرتب سازی آن جلوگیری کنیم.
اگر آرایه را مرتب کنیم و یک عنصر را فقط یک بار جستجو کنیم، انجام یک جستجوی خطی کارآمدتر است. روی آرایه مرتب نشده
اگر می خواهید در مورد الگوریتم های مرتب سازی در پایتون مطالعه کنید، ما شما را تحت پوشش قرار داده ایم!
(برچسبها به ترجمه)# python
منتشر شده در 1403-01-17 08:37:04