อัลกอริทึม การค้นหาแบบไบนารี (Binary Search) ใน PHP: คำอธิบาย ขั้นตอน และตัวอย่าง

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

ขั้นตอน:

1. เริ่มต้นช่วงการค้นหา: เริ่มต้นด้วยการเลือกช่วงการค้นหาจากตำแหน่งแรก left  ไปยังตำแหน่งสุดท้าย right  ของอาร์เรย์
2. ค้นหาจุดกึ่งกลาง: คำนวณจุดกึ่งกลางโดยหาค่าเฉลี่ย left และตำแหน่งที่เหมาะสม นี่คือจุดกึ่งกลางของช่วงการค้นหา
3. เปรียบเทียบค่า: เปรียบเทียบค่าที่จุดกึ่งกลางกับค่าเป้าหมาย
4. จับผลการเปรียบเทียบ: ถ้าค่าที่จุดกึ่งกลางตรงกับค่าเป้าหมาย ส่งคืนตำแหน่งนี้ หากค่าที่จุดกึ่งกลางน้อยกว่าค่าเป้าหมาย ให้อัปเดตตำแหน่งด้านซ้ายเป็นตรงกลาง + 1 เพื่อค้นหาด้านขวา หากค่าที่จุดกึ่งกลางมากกว่าค่าเป้าหมาย ให้อัปเดตตำแหน่งด้านขวาเป็นตรงกลาง- 1 เพื่อค้นหาครึ่งซ้าย
5. ทำซ้ำ: ทำซ้ำขั้นตอนที่ 2 ถึง 4 จนกว่าจะพบค่าหรือไม่มีองค์ประกอบให้ตรวจสอบ left > right อีก

ข้อดีและข้อเสีย

ข้อดี:

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

ข้อเสีย:

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

ตัวอย่าง: Binary Search เพื่อค้นหาค่า 12 ในอาร์เรย์ที่เรียงลำดับใน 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; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}  

คำอธิบายของตัวอย่าง

1. เราเริ่มต้นด้วยช่วงการค้นหาเริ่มต้นจากตำแหน่งแรก left = 0 ถึงตำแหน่งสุดท้าย right = 6  ของอาร์เรย์
2. เราคำนวณจุดกึ่งกลาง(กลาง) โดยเฉลี่ยตำแหน่งซ้ายและขวา mid = 3. ค่ากลางคือ 12
3. เราเปรียบเทียบค่าที่ mid(12) กับค่าเป้าหมาย(12) และพบการจับคู่ เราจึงส่งคืนตำแหน่งที่ 3
4. อัลกอริทึมสิ้นสุดลง และเราแสดงผลลัพธ์ "พบค่า 12 ที่ตำแหน่ง 3"