การค้นหาไบนารีใน JavaScript

การค้นหาแบบไบนารีคืออัลกอริทึมการค้นหาที่ใช้เพื่อค้นหาตำแหน่งขององค์ประกอบเฉพาะในรายการที่เรียงลำดับ ทำงานโดยแบ่งครึ่งรายการซ้ำๆ จนกว่าจะพบองค์ประกอบที่ต้องการหรือพบว่าองค์ประกอบนั้นไม่มีอยู่ในรายการ

การค้นหาแบบไบนารีทำงานอย่างไร

เพื่อทำความเข้าใจว่าการค้นหาไบนารีทำงานอย่างไร ลองพิจารณาตัวอย่าง สมมติว่าเรามีรายการจำนวนเต็มที่เรียงลำดับ และเราต้องการหาตำแหน่งของเลข 37 วิธีการทำงานของอัลกอริทึมการค้นหาแบบไบนารีมีดังนี้

1. อันดับแรก เรากำหนดองค์ประกอบตรงกลางของรายการ หากองค์ประกอบตรงกลางคือ 37 เราทำเสร็จแล้วและส่งคืนตำแหน่งขององค์ประกอบ
2. ถ้าองค์ประกอบตรงกลางไม่ใช่ 37 เราจะตรวจสอบว่ามากกว่าหรือน้อยกว่า 37 ถ้ามากกว่า 37 เรารู้ว่าองค์ประกอบที่ต้องการต้องอยู่ในครึ่งซ้ายของรายการ ถ้าน้อยกว่า 37 เรารู้ว่าองค์ประกอบที่ต้องการต้องอยู่ในครึ่งขวาของรายการ
3. เราทำขั้นตอนนี้ซ้ำในครึ่งที่เหมาะสมของรายการจนกว่าจะพบองค์ประกอบหรือพบว่าองค์ประกอบนั้นไม่มีอยู่ในรายการ

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

เหตุใดเราจึงควรใช้การค้นหาแบบไบนารี

เหตุใดเราจึงควรใช้การค้นหาแบบไบนารี ข้อดีหลักประการหนึ่งของการค้นหาแบบไบนารีคือความซับซ้อนของเวลา ในกรณีที่เลวร้ายที่สุด ความซับซ้อนของเวลาของการค้นหาแบบไบนารีคือ O(log n) ซึ่งหมายความว่าเร็วกว่าการค้นหาเชิงเส้น (O(n)) สำหรับรายการขนาดใหญ่มาก ทำให้เป็นอัลกอริทึมที่มีประสิทธิภาพสำหรับการค้นหาชุดข้อมูลขนาดใหญ่

โดยสรุป การค้นหาแบบไบนารีเป็นอัลกอริทึมที่มีประโยชน์สำหรับการค้นหาตำแหน่งขององค์ประกอบเฉพาะในรายการที่เรียงลำดับได้อย่างรวดเร็ว ความซับซ้อนของเวลาทำให้เหมาะสำหรับการค้นหาชุดข้อมูลขนาดใหญ่ และใช้งานได้ค่อนข้างง่ายใน JavaScript