اصلا الگوریتم چیه؟
یه مجموعه دستور هست اش برای دستیابی به یه وظیفه ای که برنامه ریزی کردیم برای انجام اش.
به عنوان مثال هر قسمت از کد میتونه یه الگوریتم باشه
نکته ای که وجود داره، پیاده سازی الگوریتم ها به احتمال زیاد در هر زبانی که دوست دارید هست اش و میتونید باهاش کار کنید؛ اما پیاده سازی ها بدون استفاده خواهند بود اگر trade off ها رو نتونید درک کنید تو این کتاب در این مورد صحبت خواهد شد
Binary Search
مثال: فکر کنید داخل یه دفترچه دنبال یه اسم هستید
که با یه حرفی شروع میشه که مثلا بدونید اون حرف در وسط های الفبا هست اش. خب اگر بخواهید بگردید
می رید از اول و شروع به گشتن میکنید؟
یا ترجیح میدید که از وسط شروع به گشتن کنید
مثال دیگه: یه لغت در دیکشنری که مثلا با حرف O شروع میشه
حالا فرض کنید میخواهید تو facebook وارد شوید و حرف اول شما برای username با کلمه ای در وسط الفبا شروع میشه
facebook میتونه از A شروع کنه یا منطقی تره از جایی در وسط دنبال اش بگرده
این یه مسئله سرچ هست اش و همه این موارد گفته شده الگوریتم های گفته شده از binary search برای حل مسئله استفاده میکنند
Binary Search
یه الگوریتم که ورودی اش یه لیست مرتب شده است اگر المنت که دنبال اش هستید در لیست باشه باینری سرچ محل اون رو بهتون میگه در غیر این صورت null برمیگردونه
ساده ترین سرچ اینه که مثلا اگر قرار باشه یک شماره ای که مدنظر من هست اش رو در کمترین حالت ممکن حدس بزنید
برای مثال اگر شماره مدنظر بین 1 تا 100 باشه
در هر بار حدس زدن میگم خیلی پایین یا خیلی بالاست یا درست هست اش
فرض کنیم شما اینطوری حدس میزنید
1و2و3و ...
این شاید ساده ترین یا احمقانه ترین حالت باشه
با هر با حدس فقط محدوده یک شماره رو از بین می برید
روش بهتر شروع از 50 هست اش
اگر آرایه مثلا 100 تایی هست همون اول نصف اش رو میگیم که مشخص بشه در چه بازه ای هست اش
پس حدس بعدی میشه بازه مونده نصف اون یعنی 75 اگر فرضا گفته شده باشه خیلی پایین همین جوری تا انتها
بعد اگر گفت 75 خیلی بالا بین 50 تا 75 نصف اش رو در نظر میگیرم
وسط بین 50 تا 75 میشه
25/2 = 12/5 همون 13 که وسط بین اون 2 عدد میشه جمع اش با 50 که میشه 63
اگر بازم مثلا گفت 63 مثلا خیلی بالاست، دوباره وسط بین اون عدد یعنی اون 13 باقی مونده میشه
13/2 = 7
بازه پایین رو چون گفته شده 63 خیلی بالاست با 7 جمع میکنیم که میشه 57 جواب درست
این کار binary search هست اش
سئوال: فکر کنید دنبال یه لغت در دیکشنری هستید دیکشنری 240000 لغت دارد در بدترین حالت چند مرتبه سرچ خواهید داشت؟
در سرچ ساده 240 هزار مرتبه اما در باینری سرچ 18 مرتبه
240k -> 120k -> 60k -> 30k -> 15k -> 7/5k -> 3750 ->1875 -> 938 -> 469 -> 235-> 118-> 59 -> 30 -> 15 ->8 -> 4-> 2 -> 1
این تعداد دفعاتی که نصف شده رو بشمری به جز شماره 1 انتهای میشه 18 مرتبه
نکته: پس برای هر لیست ازn بیانری سرچ log n یا log در پایه 2 برای n هست زمان میبره برای بدترین حالت در صورتی که سرچ ساده n مرتبه زمان میبره
نکته ریاضی: log همون بر عکس توان هست اش
مثلا چند مرتبه باید 10 رو در 10 ضرب کنیم تا 100 رو بدست بیاریم
log 100 در پایه 10 میشه 2
10 به توان 2 میشه 100
نکته: سرچ باینری زمانی کار میکنه که لیست مرتب شده باشه
