Binary Search ค้นหาในอาร์เรย์ที่ เรียงลำดับแล้ว โดยแบ่งครึ่งช่วงค้นหาเรื่อยๆ
Complexity
| Worst-case | O(log n) |
| Best-case | O(1) |
| Average | O(log n) |
| Space | O(1) |
อัลกอริทึม
public static object BinarySearch(int[] arr, int key) {
int min = 0;
int max = arr.Length - 1;
while (min <= max) {
int mid = (min + max) / 2;
if (key == arr[mid]) return mid; // คืน index (0-based)
else if (key < arr[mid]) max = mid - 1;
else min = mid + 1;
}
return -1; // ไม่เจอ
}
หมายเหตุ: โค้ดต้นฉบับมีบั๊กตัวแปร max และ min ไม่ได้ประกาศ ผมแก้ไขแล้ว และคืนค่า index แทน ++mid
ตัวอย่างการใช้งาน
int[] sorted = { 10, 20, 30, 40, 50, 60, 70 };
int index = (int)BinarySearch(sorted, 40); // คืน 3
int notFound = (int)BinarySearch(sorted, 25); // คืน -1
Built-in: Array.BinarySearch(arr, key) ใช้ได้เลย
