การนำ Binary Search มาใช้ใน JavaScript เพื่อคืนดัชนีถ้าพบตัวเลขที่ค้นหา

ภาพรวม

เราต้องเขียนฟังก์ชันที่รับอาร์เรย์ตัวเลขที่จัดเรียงแล้วเป็นอาร์กิวเมนต์แรก และตัวเลขที่ต้องการค้นหาเป็นอาร์กิวเมนต์ที่สอง หากพบ ให้คืนดัชนี มิฉะนั้นคืน -1

ใช้ Binary Search Algorithm (แบ่งครึ่งซ้ำๆ จนเหลืออิลิเมนต์เดียว) อาร์เรย์ต้องจัดเรียงแล้ว

ตัวอย่างโค้ด

const arr = [-3, -1, 4, 7, 9, 11, 14, 22, 26, 28, 36, 45, 67, 78, 88, 99];

const binarySearch = (arr = [], num) => {
  let l = 0;
  let r = arr.length - 1;
  while(l <= r) {
    const mid = Math.floor((l + r) / 2);
    if(num == arr[mid]) {
      return mid;
    } else if(num < arr[mid]) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  return -1;
};

console.log(binarySearch(arr, 22));
console.log(binarySearch(arr, 56));
console.log(binarySearch(arr, 11));

ผลลัพธ์ในคอนโซล

7 -1 5