Tìm kiếm nhị phân là một — hiệu quả; ước tính độ phức tạp của nó là O(log2(n)), trong khi tìm kiếm tuần tự thông thường có O(n). Điều này có nghĩa là, ví dụ, đối với một mảng gồm 1024 phần tử, tìm kiếm tuyến tính, trong trường hợp xấu nhất, khi phần tử mong muốn không có trong mảng, sẽ xử lý tất cả 1024 phần tử. Tìm kiếm nhị phân là đủ để xử lý các phần tử \(log_2(1024) = 10\). Kết quả này đạt được là do sau bước đầu tiên của vòng lặp, khu vực tìm kiếm thu hẹp xuống còn 512 phần tử, sau bước thứ hai – lên đến 256, v.v.
Nhược điểm của thuật toán này là yêu cầu sắp xếp dữ liệu, cũng như khả năng truy cập bất kỳ phần tử dữ liệu nào trong một khoảng thời gian không đổi (không phụ thuộc vào lượng dữ liệu). Do đó, thuật toán không thể hoạt động trên các mảng không có thứ tự và bất kỳ cấu trúc dữ liệu nào dựa trên danh sách được liên kết.
Thực hiện
tạm biệt (phải – trái > 1) // Miễn là đường viền bên phải ở bên phải bên trái
nc
giữa = (trái + phải) /< /span> 2; // Giữa khu vực tìm kiếm
nếu (A[middle] >= b) thì
phải = giữa; // Di chuyển đường viền bên phải
nếu không
trái = giữa; // Nếu không thì di chuyển đường viền bên trái
cc
nếu (A[right] == X) thì
đầu ra bên phải;
nếu không thì
đầu ra -1;
ở đâu:
A - mảng nguồn,
N - kích thước mảng,
X - số mong muốn.
|