جست‌وجوی درون‌یابی
Interpolation Searchجست‌وجوی درون‌یابی یک الگوریتم از دسته جست‌وجو است. این الگوریتم فضای جست‌وجو را پیمایش یا محدود می‌کند تا target پیدا شود یا نبودنش ثابت شود.
اول این مفهوم را در ذهن نگه دار
جست‌وجوی درون‌یابی یک الگوریتم از دسته جست‌وجو است. این الگوریتم فضای جست‌وجو را پیمایش یا محدود می‌کند تا target پیدا شود یا نبودنش ثابت شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم جست‌وجوی درون‌یابی ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع avg O(log log n), worst O(n) است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
اول پیش‌شرط‌ها را بنویس: مرتب بودن؟ توزیع؟ random access؟
بازه یا state جست‌وجو را شفاف نگه دار.
مطمئن شو هر مرحله واقعاً به termination نزدیک می‌شود.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای جست‌وجوی درون‌یابی هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
avg O(log log n), worst O(n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- الگوریتم را با structure و وضعیت preprocessing داده هماهنگ انتخاب کن.
کجا معمولاً اشتباه می‌کنیم؟
- نقض پیش‌شرط الگوریتم.
- خطای مرزی و شرط پایان.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای جست‌وجوی درون‌یابی در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی avg O(log log n), worst O(n) و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
جست‌وجوی درون‌یابی چه مسئله‌ای را حل می‌کند؟
جست‌وجوی درون‌یابی یک الگوریتم از دسته جست‌وجو است. این الگوریتم فضای جست‌وجو را پیمایش یا محدود می‌کند تا target پیدا شود یا نبودنش ثابت شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا avg O(log log n), worst O(n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نقض پیش‌شرط الگوریتم.