การค้นหาแบบทวิภาค (Binary Search) ใน JavaScript

ภาพรวม

Binary Search เป็นอัลกอริทึมค้นหาในอาร์เรย์ที่จัดเรียงแล้ว (Sorted Array) โดยแบ่งช่วงค้นหาลงครึ่งเรื่อยๆ ความซับซ้อน O(log n)

เงื่อนไข

• อาร์เรย์ต้องถูกจัดเรียงแล้ว (Ascending)
• เข้าถึงแบบ Random Access ได้ (Array รองรับ)

การนำไปใช้ (Recursive)

const arr = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23];

const binarySearch = (arr, query) => {
  let index = Math.floor(arr.length / 2);
  
  if (arr[index] === query) {
    return index;
  } else if (arr.length === 1) {
    return -1; // ไม่พบ
  } else if (arr[index] < query) {
    // ค้นหาด้านขวา
    const rightArr = arr.slice(index + 1);
    const res = binarySearch(rightArr, query);
    return res === -1 ? -1 : index + 1 + res;
  } else {
    // ค้นหาด้านซ้าย
    const leftArr = arr.slice(0, index);
    return binarySearch(leftArr, query);
  }
};

console.log(binarySearch(arr, 1));   // 0
console.log(binarySearch(arr, 7));   // 5
console.log(binarySearch(arr, 11));  // 7
console.log(binarySearch(arr, 12));  // -1 (ไม่พบ)
console.log(binarySearch(arr, 22));  // 13

ผลลัพธ์

0 5 7 -1 13

การนำไปใช้แบบ Iterative (แนะนำ - ประหยัด Memory)

const binarySearchIterative = (arr, target) => {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1; // ไม่พบ
};

วิธีการทันสมัย (ES6+)

// ใช้ Array.prototype.findIndex (แต่เป็น O(n) ไม่ใช่ Binary Search)
const findIndex = (arr, target) => arr.findIndex(x => x === target);

// Lower Bound / Upper Bound (สำหรับ Duplicate Values)
const lowerBound = (arr, target) => {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
};

const upperBound = (arr, target) => {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left;
};

การประยุกต์ใช้

• Database Index Lookup
• Auto-complete / Typeahead
• Version Control (Git Bisect)
• Numerical Methods (Root Finding)
• Game Programming (AI Decision Making)

ข้อควรระวัง

• Recursive version สร้างอาร์เรย์ใหม่ทุกครั้ง (slice) -> ใช้ Memory มาก
• Iterative version ดีกว่าสำหรับ Production
• JavaScript Array.sort() เรียงตาม Unicode code points ต้องระบุ compare function สำหรับตัวเลข