Binary Search เป็นอัลกอริทึมค้นหาแบบ Compare-and-Split เรียกอีกอย่างว่า Half-Interval Search, Logarithmic Search, Binary Chop ค้นหาตำแหน่ง Target ใน Sorted Array เปรียบเทียบ Target กับ Middle Element หากเท่ากัน คืน Index หากไม่เท่ากัน ตัดครึ่ง Array ไปค้นหาต่อ (น้อยกว่า -> ครึ่งซ้าย, มากกว่า -> ครึ่งขวา)
Input: A[] = {0,2,6,11,12,18,34,45,55,99} n=55 Output: 55 at Index = 8คำอธิบาย
เปรียบเทียบ 55 กับ Middle (18) 55 > 18 ใช้ครึ่งขวา {34,45,55,99} Middle คือ 55 ตรงกัน คืน Index 8
มี 2 วิธี Implement:
- Iterative ใช้ Loop ในฟังก์ชันตรวจสอบ Middle
- Recursive ฟังก์ชันเรียกตัวเองพร้อมค่าที่เปลี่ยนไป
ตัวอย่าง (Iterative)
#include <stdio.h>
int iterativeBsearch(int A[], int size, int element);
int main() {
int A[] = {0, 2, 6, 11, 12, 18, 34, 45, 55, 99};
int n = 55;
printf("%d is found at Index %d \n", n, iterativeBsearch(A, 10, n));
return 0;
}
int iterativeBsearch(int A[], int size, int element) {
int start = 0, end = size - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (A[mid] == element) return mid;
else if (element < A[mid]) end = mid - 1;
else start = mid + 1;
}
return -1;
}ผลลัพธ์
55 is found at Index 8
ตัวอย่าง (Recursive)
#include <stdio.h>
int RecursiveBsearch(int A[], int start, int end, int element) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (A[mid] == element) return mid;
else if (element < A[mid]) return RecursiveBsearch(A, start, mid - 1, element);
else return RecursiveBsearch(A, mid + 1, end, element);
}
int main() {
int A[] = {0, 2, 6, 11, 12, 18, 34, 45, 55, 99};
int n = 55;
printf("%d is found at Index %d \n", n, RecursiveBsearch(A, 0, 9, n));
return 0;
}ผลลัพธ์
55 is found at Index 8
