Searching

Binary Search คืออะไร

Binary Search (การค้นหาแบบทวิภาค) คืออัลกอริทึมค้นหาที่ทรงพลังสำหรับข้อมูลที่เรียงลำดับแล้ว — แทนที่จะไล่ตรวจทีละตัว (แบบ Linear Search) เราจะดูตำแหน่งกลางก่อน แล้วตัดช่วงค้นหาทิ้งครึ่งหนึ่งทันที

พูดอีกแบบ: Linear Search เหมือนเดินตรวจทุกห้องในอาคารทีละห้อง แต่ Binary Search เหมือนถามตำแหน่งกลางของช่วงที่เหลือ แล้วปิดครึ่งอาคารที่ไม่เกี่ยวทิ้งในทุกครั้งที่ตัดสินใจ

• ดูตำแหน่งกลางของช่วงค้นหา — เปรียบเทียบค่า ณ ตำแหน่งนั้นกับเป้าหมาย
• ถ้าค่ากลาง < เป้าหมาย → ตัดฝั่งซ้ายทิ้ง (เลื่อนขอบซ้ายไปที่ mid + 1)
• ถ้าค่ากลาง > เป้าหมาย → ตัดฝั่งขวาทิ้ง (เลื่อนขอบขวาไปที่ mid - 1)
• ทำซ้ำจนกว่าเจอ หรือช่วงค้นหาว่างเปล่า (ไม่พบข้อมูล)

แนวคิดหลัก: ตัดครึ่งช่วงค้นหา

หัวใจของ Binary Search คือทุกรอบที่เปรียบเทียบ เราจะตัดข้อมูลทิ้งประมาณครึ่งหนึ่งเสมอ — ทำให้จำนวนรอบที่ต้องตรวจเติบโตช้ามาก (logarithmic) แม้ข้อมูลจะมีขนาดใหญ่ขึ้นหลายเท่า

• รอบที่ 1: เหลือประมาณ n/2 ตัว
• รอบที่ 2: เหลือประมาณ n/4 ตัว
• รอบที่ 3: เหลือประมาณ n/8 ตัว
• รอบที่ k: เหลือประมาณ n/(2^k) ตัว

ตัวอย่าง: ถ้าอาเรย์มี 1,000,000 ตัว — Linear Search Worst Case ต้องดู 1,000,000 ครั้ง แต่ Binary Search ใช้เพียง ~20 ครั้งเท่านั้น

เงื่อนไขสำคัญ: ข้อมูลต้องเรียงก่อน

หากข้อมูลของคุณยังไม่เรียงลำดับ มีทางเลือก: • ใช้ Linear Search — ไม่ต้องเรียงก่อน (เหมาะกับข้อมูลน้อย) • จัดเรียงข้อมูลก่อนด้วย .sort() แล้วใช้ Binary Search (คุ้มค่าถ้าต้องค้นหาหลายครั้งในข้อมูลชุดเดียวกัน) • จัดเก็บข้อมูลให้เรียงตั้งแต่แรก — ถ้าควบคุมวิธีการเก็บข้อมูลได้

รู้จักตัวแปร left, right, mid

Binary Search ใช้ตัวแปร 3 ตัวควบคุมช่วงค้นหา — สองตัวเป็นขอบเขตที่หดเข้าหากันเรื่อย ๆ และหนึ่งตัวเป็นจุดเปรียบเทียบ

• left — ขอบซ้ายของช่วงที่กำลังค้นหา เริ่มที่ index 0
• right — ขอบขวาของช่วงที่กำลังค้นหา เริ่มที่ index สุดท้ายของอาเรย์
• mid — ตำแหน่งกลางของช่วงปัจจุบัน คำนวณด้วยสูตร: mid = left + Math.floor((right - left) / 2) เพื่อป้องกัน overflow

ทุกครั้งที่เปรียบเทียบ เราจะอัปเดต left หรือ right เพื่อ"บีบ"ช่วงค้นหาให้แคบลง — จนกว่าจะเจอเป้าหมาย หรือ left > right (ช่วงค้นหาว่างเปล่า = ไม่พบ)

ตัวอย่างการทำงานทีละรอบ

ค้นหา target = 23 ใน sorted array [3, 7, 10, 14, 18, 23, 29, 31, 40] — มาดูกันว่า Binary Search ตัดช่วงค้นหาอย่างไร

Binary Search ลดช่วงค้นหาลงครึ่งหนึ่งในแต่ละรอบ — จาก 9 ตัว → เหลือแค่ไม่กี่ตัว

• รอบที่ 1: left=0, right=8, mid=4 → values[4]=18 ซึ่ง < 23 จึงตัดฝั่งซ้ายทิ้ง → left = mid + 1 = 5
• รอบที่ 2: left=5, right=8, mid=6 → values[6]=29 ซึ่ง > 23 จึงตัดฝั่งขวาทิ้ง → right = mid - 1 = 5
• รอบที่ 3: left=5, right=5, mid=5 → values[5]=23 ตรงกับเป้าหมายพอดี → เจอแล้ว! คืน index 5

Pseudocode และโค้ด JavaScript

ฟังก์ชัน binarySearch(values, target):
  left = 0
  right = values.length - 1

  ขณะที่ left <= right:
    mid = left + floor((right - left) / 2)

    ถ้า values[mid] == target:
      คืนค่า mid

    ถ้า values[mid] < target:
      left = mid + 1
    มิฉะนั้น:
      right = mid - 1

  คืนค่า -1

function binarySearch(values, target) {
  let left = 0;
  let right = values.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (values[mid] === target) {
      return mid;
    }

    if (values[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

// ตัวอย่างการใช้งาน
const numbers = [3, 7, 10, 14, 18, 23, 29, 31, 40];

console.log(binarySearch(numbers, 23)); // 5
console.log(binarySearch(numbers, 3));  // 0
console.log(binarySearch(numbers, 40)); // 8
console.log(binarySearch(numbers, 11)); // -1
console.log(binarySearch([], 99));      // -1

อธิบายทีละส่วน: • `let left = 0; let right = values.length - 1` — ตั้งขอบเขตเริ่มต้นคลุมทั้งอาเรย์ • `while (left <= right)` — วน loop ตราบใดที่ช่วงค้นหายังไม่ว่าง (left ยังไม่เกิน right) • `mid = left + Math.floor((right - left) / 2)` — คำนวณตำแหน่งกลางแบบป้องกัน overflow • ถ้า `values[mid] === target` → return mid (เจอแล้ว) • ถ้า `values[mid] < target` → เป้าหมายอยู่ทางขวา → เลื่อน left ไป mid + 1 • ถ้า `values[mid] > target` → เป้าหมายอยู่ทางซ้าย → เลื่อน right ไป mid - 1 • หลัง loop → return -1 (ช่วงว่าง = ไม่มี target ในอาเรย์)

ดูโค้ดทำงานทีละขั้นด้วย Code Trace

ประสิทธิภาพ (Time & Space Complexity)

• Best Case: O(1) — target อยู่ที่ตำแหน่งกลางพอดีตั้งแต่รอบแรก
• Average Case: O(log n) — โดยเฉลี่ยต้องตัดครึ่งหลายรอบก่อนเจอ
• Worst Case: O(log n) — ไม่เจอเลย หรือเจอช้าสุด แต่จำนวนรอบยังเติบโตแบบ logarithm

Space Complexity = O(1) — ฟังก์ชันแบบ iterative ใช้ตัวแปร left, right, mid เท่านั้น ไม่ต้องสร้างโครงสร้างข้อมูลใหม่

ข้อดี ข้อจำกัด และกรณีใช้งาน

เปรียบเทียบ Linear Search กับ Binary Search

ข้อผิดพลาดที่พบบ่อย

กฎสำคัญที่ต้องจำ

ทบทวนความเข้าใจ

แบบฝึกหัด: ฝึกเขียน Binary Search

แบบฝึกหัด 3 ข้อนี้จะช่วยให้คุณเขียน Binary Search ได้คล่อง — เริ่มจากการค้นหามาตรฐาน ไปจนถึงการหา first/last position และ search insert