Tìm kiếm nhị phân hoạt động trên mảng đã sắp xếp. Giá trị được so sánh với phần tử giữa của mảng. Nếu không tìm thấy bằng nhau, thì nửa phần mà giá trị không nằm trong đó bị loại bỏ. Cách tương tự, nửa phần còn lại được tìm kiếm.
Đây là phần tử giữa trong mảng của chúng ta. Giả sử chúng ta cần tìm 62, thì phần bên trái sẽ bị loại bỏ và phần bên phải sau đó được tìm kiếm:
Đây là các độ phức tạp của tìm kiếm nhị phân:
| Worst-case performance |
O(log n) |
| Best-case performance |
O(1) |
| Average performance |
O(log n) |
| Worst-case space complexity |
O(1) |
Ví dụ
Hãy xem phương thức triển khai tìm kiếm nhị phân:
public static object BinarySearchDisplay(int[] arr, int key) {
int minNum = 0;
int maxNum = arr.Length - 1;
while (minNum <= maxNum) {
int mid = (minNum + maxNum) / 2;
if (key == arr[mid]) {
return ++mid;
} else if (key < arr[mid]) {
maxNum = mid - 1;
} else {
minNum = mid + 1;
}
}
return "None";
}