การค้นหาข้อมูลด้วย Binary Search ในภาษา PHP

 

ในโลกของการเขียนโปรแกรม เมื่อเราต้องการค้นหาข้อมูลในกลุ่มข้อมูลที่เรียงลำดับแล้ว มีวิธีการมากมายในการค้นหา โดยหนึ่งในวิธีที่มีประสิทธิภาพมากที่สุดก็คือ Binary Search หรือการค้นหาทวินาม ซึ่งให้ประสิทธิภาพในการค้นหาที่เหนือกว่าการค้นหาด้วยวิธี linear search โดยเฉพาะเมื่อกลุ่มข้อมูลมีขนาดใหญ่

 

Binary Search คืออะไร?

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

 

วิธีการทำงานของ Binary Search

1. เริ่มต้นที่ตำแหน่งกลางของรายการข้อมูล

2. เปรียบเทียบค่าที่ค้นหากับค่าที่ตำแหน่งกลาง

- ถ้าค่าที่ค้นหามีค่าตรงกับค่าที่ตำแหน่งกลาง แสดงว่าพบแล้ว

- ถ้าค่าที่ค้นหาต่ำกว่าค่าที่ตำแหน่งกลาง ให้ทำการค้นหาต่อในครึ่งซ้าย

- ถ้าค่าที่ค้นหามีค่ามากกว่าค่าที่ตำแหน่งกลาง ให้ทำการค้นหาต่อในครึ่งขวา

3. ทำขั้นตอนนี้ซ้ำจนกว่าจะพบค่าหรือจนกว่าจะไม่มีข้อมูลเหลือให้ค้นหา

 

ตัวอย่าง Code ในภาษา PHP

มาดูตัวอย่างการใช้งาน Binary Search ด้วย PHP กัน:

 function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);

        // ค่าตรงกลางเท่ากับค่าเป้าหมาย
        if ($arr[$mid] == $target) {
            return $mid; // คืนค่าตำแหน่งของเป้าหมาย
        }
        // ค่าตรงกลางน้อยกว่าเป้าหมาย
        elseif ($arr[$mid] < $target) {
            $left = $mid + 1; // ค้นหาครึ่งขวา
        }
        // ค่าตรงกลางมากกว่าเป้าหมาย
        else {
            $right = $mid - 1; // ค้นหาครึ่งซ้าย
        }
    }

    return -1; // ไม่พบค่าเป้าหมาย
}

// ตัวอย่างการเรียกใช้งาน
$arr = [1, 3, 5, 7, 9, 11, 13, 15];
$target = 7;

$result = binarySearch($arr, $target);

if ($result != -1) {
    echo "พบ $target ที่ตำแหน่ง $result";
} else {
    echo "ไม่พบ $target";
}

 

Use Case ของ Binary Search

การค้นหาแบบ Binary Search มักจะใช้ในหลายสถานการณ์ เช่น:

- การค้นหาในฐานข้อมูล: ใช้เมื่อต้องการค้นหาข้อมูลในชุดข้อมูลที่มีขนาดใหญ่ เช่น ระบบการจัดการฐานข้อมูลที่ต้องการค้นหาข้อมูลจากแถวหรือคอลัมน์ - การค้นหาข้อมูลในอาเรย์ที่ถูกจัดเรียง: ในเกมหรือแอปพลิเคชันต่าง ๆ ที่ต้องการค้นหาค่าสถานะ เช่น การค้นหาคะแนนในตารางอันดับ

 

การวิเคราะห์ Complexity

- Time Complexity: O(log n) – เพราะว่าแต่ละครั้งที่ค้นหาจะลดจำนวนข้อมูลที่ต้องค้นหาได้ครึ่งหนึ่ง - Space Complexity: O(1) – การใช้หน่วยความจำไม่ขึ้นอยู่กับขนาดของข้อมูลหลัก

 

ข้อดีของ Binary Search

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

 

ข้อเสียของ Binary Search

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

 

สรุป

Binary Search เป็นอัลกอริธึมที่มีประสิทธิภาพและเหมาะสำหรับการค้นหาข้อมูลในกลุ่มที่ถูกจัดเรียงอยู่แล้ว หากคุณอยากเรียนรู้เกี่ยวกับอัลกอริธึมเพิ่มเติม หรือพัฒนาทักษะในการเขียนโปรแกรมอย่างมืออาชีพ สามารถเข้ามาศึกษาได้ที่ EPT (Expert-Programming-Tutor) ที่เรามีหลักสูตรที่หลากหลาย และมีผู้สอนที่มีความเชี่ยวชาญที่จะช่วยให้คุณเข้าใจได้อย่างถ่องแท้ ในทุกขั้นตอนของการเรียนรู้การเขียนโปรแกรม ไม่พลาดโอกาสในการพัฒนาและเสริมสร้างทักษะของคุณไปกับเรา!

 

 

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