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

معرفی

جستجوی باینری یک الگوریتم جستجوی کارآمد است که کار می کند روی آرایه های مرتب شده اغلب به عنوان یکی از اولین نمونه های الگوریتم هایی که در زمان لگاریتمی اجرا می شوند استفاده می شود (O(logn)) به دلیل رفتار شهودی آن و یک الگوریتم اساسی در علوم کامپیوتر است.

در این مقاله، ما به ایده پشت و اجرای پایتون خواهیم پرداخت جستجوی باینری.

جستجوی باینری – مثال

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

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

قبل از اینکه به توضیح چگونگی کارکرد جستجوی باینری ادامه دهیم، اجازه دهید به یک مثال سریع نگاه کنیم:

همانطور که می بینیم، ما با اطمینان می دانیم که از آنجایی که آرایه مرتب شده است، عنصر مورد نظر ما (18) در نیمه اول آرایه اصلی نیست.

وقتی می دانیم که در کدام نیمی از آرایه اصلی قرار دارد x است، ما می توانیم این را دقیقا تکرار کنیم process با آن نیمه و دوباره آن را به دو نیم تقسیم کنید، نیمه ای که مطمئناً حاوی آن نیست را دور بریزید x:

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

اگر به این موضوع دقت کنید، می توانید متوجه شوید که در بدترین حالت (x در آرایه وجود ندارد)، ما باید تعداد بسیار کمتری از عناصر را نسبت به یک آرایه مرتب نشده بررسی کنیم – که به چیزی بیشتر در طول خطوط نیاز دارد. جستجوی خطی، که به طرز دیوانه کننده ای ناکارآمد است.

برای دقیق تر، تعداد عناصری که باید در بدترین حالت بررسی کنیم، است O(log₂ن) جایی که ن تعداد عناصر آرایه است.

هر چه آرایه بزرگتر باشد، تأثیر بیشتری می گذارد:

اگر آرایه ما 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)

بیایید نگاهی دقیق تر به این کد بیندازیم. اگر از بازگشت خارج می شویم 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

نتیجه

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

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

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

اگر می خواهید در مورد الگوریتم های مرتب سازی در پایتون مطالعه کنید، ما شما را تحت پوشش قرار داده ایم!