Binary Search - Beyond Sorted Arrays
ראיון ב-Spotify, 2022: "Find the minimum capacity of a ship to deliver all packages within D days." 90% מהמועמדים לא זיהו שזה Binary Search. הם ניסו DP, Greedy, ו-BFS. מועמד שהבין ש-"Binary Search על התשובה" הוא Pattern - כתב פתרון אלגנטי ב-20 דקות.
Binary Search הוא Pattern שנראה "פשוט" כי כולם מכירים את הגרסה הבסיסית על מערך ממוין. הForce Multiplier הוא להבין שBinary Search עובד על כל מרחב מונוטוני - לא רק על מערך. ברגע שמבינים את זה, כמות הבעיות שBinary Search פותר גדלה פי 5.
Binary Search הוא לא רק "מצא איבר במערך ממוין". זה Pattern רחב יותר: כל פעם שמרחב החיפוש הוא מונוטוני - כלומר, אם תשובה X תקינה אז X+1 גם תקינה (או גם לא) - Binary Search עובד.
הPower של Binary Search מגיע מהיכולת להפוך O(n) חיפוש ל-O(log n) על ידי ניצול Monotonicity. בגרסה "על התשובה" - הMagic הוא להבין שלא מחפשים ב-Array, אלא מחפשים בSpace של הפתרונות האפשריים. Koko Eating Bananas לא מחפש ב-Array של הפילים - מחפש במרחב של Speeds מ-1 עד max(piles). Capacity to Ship לא מחפש ב-Array של המשקלים - מחפש במרחב של Capacities מ-max(weights) עד sum(weights).
ברגע שמבינים ש"מרחב הפתרונות" הוא מה שעובדים עליו, ו-Binary Search עובד על כל מרחב מונוטוני - מספר השאלות שBinary Search פותר גדל פי 5. כל שאלה שמכילה "find minimum X such that condition(X) is True" - זה Binary Search. לא DP, לא Greedy, לא BFS. Binary Search. זיהוי הPattern הזה בזמן ריאלי הוא מה שמבדיל.