חיפוש בינארי - לא רק על מערך ממוין

חיפוש בינארי (Binary Search) ידוע כאלגוריתם ל-O(log n) על מערך ממוין - אבל הוא חזק הרבה יותר מזה. כל בעיה שיש לה 'תנאי מונוטוני' (אמת עד נקודה מסוימת, שקר אחרי) ניתנת לפתרון בחיפוש בינארי.

המימוש הקלאסי - ושגיאות נפוצות

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // לא (left+right)/2 - גלישת מספרים!
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // לא נמצא
}

מציאת גבול - Lower Bound ו-Upper Bound

לעיתים רוצים למצוא לא ערך מדויק אלא את הגבול: הופעה ראשונה של ערך, או הופעה אחרונה. שני הגרסאות שונות ברגע אחד קטן:

// Lower Bound: האינדקס הראשון שגדול-או-שווה ל-target
function lowerBound(arr, target) {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left; // אינדקס הופעה ראשונה, או arr.length אם לא קיים
}

Search on Answer - הכוח האמיתי

במקום לחפש ערך במערך, מחפשים את התשובה עצמה בטווח ערכים. אם ניתן לבדוק 'האם תשובה X אפשרית?' ב-O(n), ניתן למצוא את ה-X האופטימלי ב-O(n log n) סך הכל.

// בעיה: כמה ימים לחלק bananas כך שכל יום אוכלים לכל היותר k?
// (LeetCode: Koko Eating Bananas)
function minEatingSpeed(piles, h) {
  let left = 1, right = Math.max(...piles);
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const days = piles.reduce((s, p) => s + Math.ceil(p / mid), 0);
    if (days <= h) right = mid; // mid אפשרי, נסה קטן יותר
    else left = mid + 1;        // mid קטן מדי
  }
  return left;
}

בעיות קלאסיות של Search on Answer

• Koko Eating Bananas - מציאת מהירות אכילה מינימלית
• Capacity to Ship Packages - קיבולת ספינה מינימלית
• Split Array Largest Sum - חלוקת מערך ל-k חלקים עם סכום מקסימלי מינימלי
• Find the Minimum in Rotated Sorted Array - חיפוש בינארי על מערך מסובב

סיבוכיות