Binary Search แบบ Recursive ใน Java

Recursive Binary Search

ค้นหาแบบแบ่งครึ่ง (Divide & Conquer) ใช้ Recursion แทน Loop ต้องการ Sorted Array

ตัวอย่างโค้ด

public class Demo { 
    int recursiveBinarySearch(int[] arr, int left, int right, int target) { 
        if (right >= left) { 
            int mid = left + (right - left) / 2; // ป้องกัน overflow
            
            if (arr[mid] == target) 
                return mid; // เจอ
            
            if (arr[mid] > target) 
                return recursiveBinarySearch(arr, left, mid - 1, target); // ค้นซ้าย
            
            return recursiveBinarySearch(arr, mid + 1, right, target); // ค้นขวา
        } 
        return -1; // ไม่เจอ
    } 
    
    public static void main(String args[]) { 
        Demo obj = new Demo(); 
        int[] arr = {56, 78, 90, 32, 45, 99, 104}; 
        
        // ⚠️ ต้องเรียงก่อน! Binary search ต้องการ sorted array
        Arrays.sort(arr); 
        System.out.println("Sorted array: " + Arrays.toString(arr)); 
        
        int target = 104; 
        int result = obj.recursiveBinarySearch(arr, 0, arr.length - 1, target); 
        
        if (result == -1) 
            System.out.println("ไม่พบ " + target + " ในอาร์เรย์"); 
        else 
            System.out.println("พบ " + target + " ที่ index " + result); 
    } 
}

ผลลัพธ์

Sorted array: [32, 45, 56, 78, 90, 99, 104]
พบ 104 ที่ index 6

⚠️ ข้อสังเกตสำคัญ

โค้ดต้นฉบับ ไม่ได้เรียงอาร์เรย์ก่อนค้นหา Binary Search ต้องการ Sorted Array เท่านั้น มิฉะะผลลัพธ์จะผิด

Iterative Version (แนะนำสำหรับ Production)

static int binarySearchIterative(int[] arr, int target) { 
    int left = 0, right = arr.length - 1; 
    while (left <= right) { 
        int mid = left + (right - left) / 2; 
        if (arr[mid] == target) return mid; 
        if (arr[mid] < target) left = mid + 1; 
        else right = mid - 1; 
    } 
    return -1; 
}

Java Built-in

// Primitive arrays
int index = Arrays.binarySearch(arr, target); 

// Object arrays (ต้อง Comparable)
int index = Arrays.binarySearch(objArr, target); 

// With Comparator
int index = Arrays.binarySearch(arr, 0, len, target, comparator);

ความซับซ้อน

Overflow-Safe Mid Calculation

// ❌ อาจ overflow: (left + right) / 2
// ✅ ปลอดภัย:
int mid = left + (right - left) / 2; 
// หรือ Java 8+
int mid = (left + right) >>> 1; // unsigned right shift

Variants

• Lower Bound: หา index แรกที่ >= target
• Upper Bound: หา index แรกที่ > target
• First/Last Occurrence: หาตำแหน่งแรก/สุดท้ายของค่าที่ซ้ำกัน