⭕️ Binary Searching

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

🔻 این الگوریتم فقط مختص پایتون نیست و در سایر زبان ها نیز قابل پیاده‌سازی است. نکته‌ای که وجود دارد این است که حتما باید لیست sort (مرتب) شده باشد و در غیر اینصورت این متد کاربردی ندارد.

🔷 در حالت عادی برای بررسی وجود داشتن یا نداشتن یک آیتم در یک لیست (غیر از متدهایی که وجود دارد) روی لیست حلقه for پیاده سازی می‌کنید و تمام موارد موجود داخل لیست بررسی می‌شود که در این حالت روند به کندی پیش میرود و البته دیتاهایی که معمولا ما با آن‌ها سروکار داریم آن‌چنان بزرگ نیستند ولی برای دیتاهای خیلی بزرگ این روش اصلا بهینه نیست، چون تمام آیتم‌ها را بررسی می‌کند و اگر این لیست یک میلیارد آیتم داشته باشد و آیتم مورد نظر ما دقیقا وسط لیست قرار گرفته باشد باید 500 میلیون آیتم بررسی کند تا به مقدار درست برسد که این اصلا بهینه نیست و performance را به شدت پایین می‌آورد. حتی استفاده از متدهایی که وجود دارد برای این کار با این حجم از دیتا اصلا کار درستی نیست و به شدت روی performance تاثیر می‌گذارد و اگر این حالت به صورت binary searching پیاده سازی کنید دقیقا از وسط شروع می‌کند و خیلی سریع‌تر به جواب می‌رسید.

🔴 نحوه استفاده از Binary searching:

🔸 ابتدا سه متغیر تعریف می کنیم.

first = 0 # نقطه شروع لیست
last = len(lys)-1 # نقطه پایان لیست
index = -1 # ایندکس آیتم در صورت وجود، که پیش فرض وجود نداره

🔸 سپس یک حلقه بی‌نهایت ایجاد می‌کنیم و تا زمانی که first از last کمتر و مساوی باشد و مقدار index برابر -1 باشد این حلقه اجرا می‌شود و زمانی که index مقدارش عوض شود یعنی آیتم پیدا شده و نیاز به ادامه نیست.

while (first <= last) and (index == -1)

🔸 سپس مقدار first + last و تقسیم به 2 بدون قسمت اعشار که با این کار به جای اینکه از ابتدای لیست شروع کند از وسط لیست شروع می کند.

mid = (first + last) // 2 

if lys[mid] == val: 
    index = mid

elif val < lys[mid]:
    last = mid - 1

else: 
    first = mid + 1

🔸 در شرط‌های ایجاد شده بررسی می کنیم که مقدار اگر برابر با val بود، index برابر با mid شود. اگر val کمتر از مقدار آن ایندکس بود، مقدار last برابر با mid - 1 شود. و اگر مقدار val بیشتر از آن بود، first برابر با mid + 1 شود. با این روش فقط نصف ایتم ها را بررسی می کنیم.

🔸 این حالت فقط روی اعداد قابل پیاده سازی است.

#Algorithm #Binary_searching
#الگوریتم

👤 black@root

💎 Channel: @DevelopixPython