جستوجوی دودویی
Binary SearchBinary Search در یک فضای مرتبشده با هر مقایسه نصف محدوده باقیمانده را حذف میکند تا به target برسد.
اول این مفهوم را در ذهن نگه دار
Binary Search در یک فضای مرتبشده با هر مقایسه نصف محدوده باقیمانده را حذف میکند تا به target برسد.
چطور کار میکند؟ ساده و مرحلهای
target را با عنصر وسط مقایسه میکنیم.
اگر target کوچکتر بود نیمه راست و اگر بزرگتر بود نیمه چپ را کنار میگذاریم.
الگوریتم را به شکل تصمیمهای پشت سر هم بخوان
left و right را مشخص کن.
mid را داخل همین بازه حساب کن.
بعد از هر مقایسه دقیقاً یکی از مرزها را جلو ببر تا مقدار پیدا شود یا left از right عبور کند.
برای پیدا کردن 23 در [3, 8, 12, 23, 31, 44] ابتدا وسط بررسی میشود و بعد فقط نیمهای میماند که 23 هنوز میتواند داخل آن باشد.
function binarySearch(items, target) {
let left = 0;
let right = items.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (items[mid] === target) return mid;
if (items[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}syntax را حفظ نکن. stateای را که در هر خط تغییر میکند دنبال کن و آن را به invariant توضیحدادهشده در بالا وصل کن.
O(log n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرضهای preprocessing نتیجه بگیر.
موارد مناسب
- الگوریتم را با structure و وضعیت preprocessing داده هماهنگ انتخاب کن.
کجا معمولاً اشتباه میکنیم؟
- استفاده روی داده نامرتب.
- خطاهای off-by-one و loop بینهایت.
- مشخص نکردن inclusive بودن مرزها.
مدل یک پاسخ حرفهای
در جواب حرفهای invariant را بگو: اگر target وجود داشته باشد، داخل بازه فعلی است. هر مقایسه بازه را نصف میکند ولی این invariant را حفظ میکند.
جستوجوی دودویی چه مسئلهای را حل میکند؟
Binary Search در یک فضای مرتبشده با هر مقایسه نصف محدوده باقیمانده را حذف میکند تا به target برسد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایجترین اشتباه چیست؟
استفاده روی داده نامرتب.