الگوریتم جست و جوی دودویی (binary search) چیه؟

mohsen akbari — Fri, 23 Jun 2023 19:13:00 +0330

مفهوم خود الگوریتم به صورت خلاصهالگوریتم در واقع مجموعه ای از دستور العمل ها برای انجام کاری یا حل مشکلی هست.می شه گفت در واقع هر قطعه کد داخل کدنویسی یک الگوریتم هست.در برنامه نویسی بهتره که قبل از اینکه مستقیم بریم سراغ کد، یک کاغذ بزاریم جلومون و شروع کنیم به چیزهایی مورد نیاز هست.مثلا ما نیاز داریم به طراحی یک پروفایل کاربری :همیشه باید دیدگاه ماژولار داشه باشیم به مشکلات یا فیچرها(کدهایی که میخوایم برنامه نویسی کنیم فرضا سیستم ورود و ثبت نام). پس باید ببینیم این پنل کاربری چه فیچر هایی لازم داره؟1.کاربر بتونه در یک نمای کلی فعالیت هاشو در صفحه پنل کاربری ببینه.2.کاربر بتونه آخرین سفارش ها رو ببینه.3.کاربر بتونه تمام صورت حساب های مالی که از سایت رو خرید کرده ببینه.4. کاربر بتونه بره داخل پروفایل و اطلاعات کاربری خودشو تغییر بده و...حالاکه تمام فیچر های سایت رو در آوردیم سعی می کنیم باز هم مثل یک پازل تیکه تیکه کنیم(ماژولار کردن)مثلا یکی از فیچر ها بود :2.کاربر بتونه آخرین سفارش ها رو ببینه.حالا باز میایم دقیق تر نیازمندی ها رو بررسی می کنیم.دقیقا چه فیچرهایی لازمه برای این ماژول :ما در پنل یک tab داریم به اسم مالی . یک جدول نیاز هست از تمام فعالیت های مالی کاربر با این ستون ها :تاریخ - مبلغ _ وضعیت سفارش - قابلیت دانلود به صورت pdf یا excel و ....الگوریتم مجموعه ای از ریز ترین کارهایی هست که لازمه انجام بشه تا بتونیم یک فیچری رو پیاده سازی کنیم. مثلا فیچر اکسپورت گرفتن از سفارش خاصی :حالا شروع می کنیم براش الگوریتم بنویسیم :(من مراحل رو به صورت کلی میگم نه دقیق)مرحله اول : درست کردن یک button مرحله دوم : متن button باید خروجی با pdf باشدمرحله سوم : وقتی کاربر روی این دکمه کلیک کرد فایل به صورت pdf دانلود شود.مرحله چهارم : استفاده از کتابخانه X برای تبدیل این اطلاعات به pdfو.....حالا زمانی هست که شروع می کنیم به کد نویسی. پس فهمیدیم که الگوریتم یعنی مجموعه ای از دستور العمل ها(کد) برای انجام یک کاری یا پیاده سازی ماژول خاصی.الگوریتم جست و جوی دودوییالگوریتم های زیادی وجود داره و تو این تاپیک ما binary search کار داریم :با مثال شروع می کنیم :فرض کنید یک دفترچه تلفن دارید و قصد دارید دنبال این شخص بگردید "یزدانی".خب یک راه حل این هست که بشینیم از اول حروف الفبا رو بریم جلو تا برسیم به اخرش و این فامیلی رو پیدا کنیم (linear algorithm)یک راه حل دیگه این هست که از وسط شروع به گشتن کنی ( binary search algorithm )یا یک مثال دیگه :فرض کنید شما یک کاربری دارید داخل سایتتون با یوزر نیم : mohsenakbوقتی این شخص میاد داخل سایت login کنه باید داخل دیتابیس از وجود این کاربر با این اطلاعات مطمئن شد. دیتابیس می تونه از حرف A شروع کنع تمام کاربران رو بگرده یا بهتره که از میانه لیست شروع کنه بگرده؟اینجاس که الگوریتم جست و جوی دودویی میاد به کمک مایک نکته خیلی مهم این هست که ما زمانی می توانیم از binary search ها استفاده کنیم که دیتاها در یک لیست مرتب شده باشند(آرایه سورت شده نه لیست پیوندی) و اگر لیست مرتب نشده باشد این الگوریتم کارایی ندارد.فرض کنید یک آرایه داریم از 1تا 100 : [1,2,3,100]و قرار هست دنبال عدد 51 بگردیم:الگوریتم خطی یا linear algorithm به ما میگه از 0 شروع کن و دونه دونه بگرد تا برسی به این عدد (پس با این روش ما نیاز داریم 51 بار حدس بزنیم تا به جواب درست برسیم)الگوریتم جست و جوی دودویی راه حلی که برای این مشکل داره جالبه :میگه که حاجی تو بیا اول لیستی که داری رو مرتب کن (نزولی به صعودی) بعد بیا دامنه حدس هایی که میزنی رو با هر حدس نصفش کنیعنی چی؟خب ما میام با این الگوریتم این مساله رو حل کنیم:قدم اول : پیدا کردن میانه لیست که میشه خونه با ایندکس 50 که عدد 50 داخلشه. قدم دوم : چک کردن عدد مورد نظر (که 51 بود) با عدد میانه لیست (50). خب ما میایم چک می کنیم ببینیم بزرگتره یا کوچیک تره. می بینیم که عدد انتخابی ما از عددی که پیدا کردیم بزرگتره (50 < 51)قدم سوم : حذف تمام عدد هایی که از 50 کوچکتر هستندجالب شد؟ الان ما لازمه فقط 50 خونه دیگه رو بگردیم و تازه فقط یک حدس زدیم.قدم چهارم : دوباره میانه لیست جدید رو پیدا می کنیم(که میشه از 50 تا 100) و فرایند قبلی رو ادامه میدیم و...اینطوری با تعداد حدس کمتر و با یک الگوریتم تر تمیز می تونیم کد بهینه تری بنویسیم

نوشته های mohsen akbari

الگوریتم جست و جوی دودویی (binary search) چیه؟