อัลกอริทึม การค้นหาแบบไบนารี (Binary Search) ใน Java

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

อัลกอริธึมการค้นหาแบบไบนารีทำงานอย่างไร

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

ข้อดีและข้อเสียของอัลกอริทึมการค้นหาแบบไบนารี

ข้อดี:

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

ข้อเสีย:

• ข้อกำหนดอาร์เรย์ที่เรียงลำดับ: อัลกอริธึมใช้งานได้กับอาร์เรย์ที่เรียงลำดับเท่านั้น

ตัวอย่างและคำอธิบาย

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

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}  

ในตัวอย่างนี้ เราใช้อัลกอริทึมการค้นหาแบบไบนารีเพื่อค้นหาตัวเลข 9 ในอาร์เรย์จำนวนเต็มที่เรียงลำดับแล้ว อัลกอริทึมจะวนซ้ำผ่านอาร์เรย์และเปรียบเทียบค่าการค้นหากับค่าตรงกลาง ในกรณีนี้ หมายเลข 9 จะอยู่ที่ตำแหน่ง 4(ดัชนีฐาน 0) ในอาร์เรย์

แม้ว่าตัวอย่างนี้จะแสดงให้เห็นว่า Binary Search Algorithm สามารถค้นหาองค์ประกอบในอาร์เรย์จำนวนเต็มที่เรียงลำดับได้อย่างไร แต่ยังสามารถนำไปใช้กับสถานการณ์การค้นหาอื่นๆ ใน Java การเขียนโปรแกรม ได้อีกด้วย