Tìm kiếm nhị phân hoạt động trên một mảng được 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ì một nửa phần bị loại bỏ trong đó giá trị không có ở đó. Theo 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 tôi. 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 sẽ được tìm kiếm -
Đây là những phức tạp của tìm kiếm nhị phân -
| Hiệu suất trường hợp tệ nhất | O (log n) |
| Hiệu suất trường hợp tốt nhất | O (1) |
| Hiệu suất trung bình | O (log n) |
| Độ phức tạp không gian trong trường hợp xấu nhất | O (1) |
Ví dụ
Hãy để chúng tôi xem phương pháp 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]) {
max = mid - 1;
}else {
min = mid + 1;
}
}
return "None";
}