การค้นหาแบบทวิภาค (Binary Search) แบบ Recursive และ Iterative ในภาษา C

Binary Search (การค้นหาแบบทวิภาค) เป็นอัลกอริทึมค้นหาตำแหน่งของสมาชิก (target value) ในอาร์เรย์ที่จัดเรียงแล้ว อาร์เรย์ต้องจัดเรียงก่อนใช้ binary search

ชื่ออื่น: logarithmic search, binary chop, half interval search

การทำงาน

เปรียบเทียบสมาชิกที่ต้องการค้นหากับสมาชิกกลางของอาร์เรย์ และดำเนินการตามผลเปรียบเทียบ:

• Case 1 - สมาชิก = กลาง: พบแล้ว คืนค่าดัชนี
• Case 2 - สมาชิก > กลาง: ค้นหาในซับอาร์เรย์จาก middle+1 ถึง n
• Case 3 - สมาชิก < กลาง: ค้นหาในซับอาร์เรย์จาก 0 ถึง middle-1

อัลกอริทึม

Parameters: initial_value, end_value
Step 1: หาสมาชิกกลาง middle = initial_value + end_value / 2
Step 2: ถ้า middle = element คืนค่า 'found' และดัชนี
Step 3: ถ้า middle > element เรียกฟังก์ชันใหม่ end_value = middle - 1
Step 4: ถ้า middle < element เรียกฟังก์ชันใหม่ start_value = middle + 1
Step 5: ออก

การเรียกฟังก์ชันซ้ำมี 2 แบบ:

• Iterative (วนลูป)
• Recursive (เรียกฟังก์ชันตัวเอง)

โปรแกรม Binary Search แบบ Iterative

#include <stdio.h>

int iterativeBinarySearch(int array[], int start_index, int end_index, int element) {
    while (start_index <= end_index) {
        int middle = start_index + (end_index - start_index) / 2;
        if (array[middle] == element)
            return middle;
        if (array[middle] < element)
            start_index = middle + 1;
        else
            end_index = middle - 1;
    }
    return -1;
}

int main(void) {
    int array[] = {1, 4, 7, 9, 16, 56, 70};
    int n = 7;
    int element = 16;
    int found_index = iterativeBinarySearch(array, 0, n - 1, element);
    if (found_index == -1)
        printf("Element not found in the array ");
    else
        printf("Element found at index : %d", found_index);
    return 0;
}

เอาต์พุต

Element found at index : 4

โปรแกรม Binary Search แบบ Recursive

#include <stdio.h>

int recursiveBinarySearch(int array[], int start_index, int end_index, int element) {
    if (end_index >= start_index) {
        int middle = start_index + (end_index - start_index) / 2;
        if (array[middle] == element)
            return middle;
        if (array[middle] > element)
            return recursiveBinarySearch(array, start_index, middle - 1, element);
        return recursiveBinarySearch(array, middle + 1, end_index, element);
    }
    return -1;
}

int main(void) {
    int array[] = {1, 4, 7, 9, 16, 56, 70};
    int n = 7;
    int element = 9;
    int found_index = recursiveBinarySearch(array, 0, n - 1, element);
    if (found_index == -1)
        printf("Element not found in the array ");
    else
        printf("Element found at index : %d", found_index);
    return 0;
}

เอาต์พุต

Element found at index : 3