Tìm kiếm nhị phân
Tìm kiếm nhị phân (Binary Search) là một giải thuật tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο(log n). Giải thuật tìm kiếm nhị phân làm việc dựa trên nguyên tắc chia để trị (Divide and Conquer). Để giải thuật này có thể làm việc một cách chính xác thì tập dữ liệu nên ở trong dạng đã được sắp xếp.
Binary Search tìm kiếm một phần tử cụ thể bằng cách so sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy kết nối thì chỉ mục của phần tử được trả về. Nếu phần tử cần tìm là lớn hơn giá trị phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa; nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ tiếp tục như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này.
Tìm kiếm nhị phân hoạt động như thế nào?
Để tìm kiếm nhị phân hoạt động, bắt buộc phải sắp xếp mảng đích. Chúng ta sẽ tìm hiểu quá trình tìm kiếm nhị phân với một ví dụ bằng hình ảnh. Sau đây là mảng được sắp xếp của chúng tôi và chúng tôi giả sử rằng chúng tôi cần tìm kiếm vị trí của giá trị 31 bằng cách sử dụng tìm kiếm nhị phân.
Đầu tiên, chúng ta sẽ xác định một nửa mảng bằng cách sử dụng công thức này:
mid = low + (high - low) / 2
Đây là 0 + (9 - 0) / 2 = 4 (giá trị nguyên là 4,5). Vì vậy, 4 là giữa của mảng.
Bây giờ chúng ta so sánh giá trị phần tử giữa với phần tử cần tìm. Giá trị phần tử giữa là 27 và phần tử cần tìm là 31, do đó là không kết nối. Bởi vì giá trị cần tìm là lớn hơn nên phần tử cần tìm sẽ nằm ở mảng con bên phải phần tử giữa.
Chúng ta thay đổi mức thấp thành mid + 1 và tìm lại giá trị mid mới.
low = mid + 1
mid = low + (high - low) / 2
Mid mới của chúng ta là 7. Chúng ta so sánh giá trị được lưu trữ tại vị trí 7 với giá trị 31.
Giá trị được lưu trữ tại vị trí 7 không phải là một kết quả khớp, thay vào đó là nhiều hơn những gì chúng ta đang tìm kiếm. Vì vậy, giá trị phải nằm ở phần dưới từ vị trí này.
Do đó, chúng tôi tính toán lại giữa. Lần này là 5.
So sánh giá trị tại chỉ mục 5 với giá trị cần tìm và thấy rằng nó kết nối.
Chúng tôi kết luận rằng giá trị đích 31 được lưu trữ tại vị trí 5.
Tìm kiếm nhị phân giảm một nửa các mục có thể tìm kiếm và do đó làm giảm số lượng so sánh được thực hiện với số lượng rất ít.
Mã code
Mã code của thuật toán tìm kiếm nhị phân như sau:
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure
- Hiếu Kiều -
Bài viết nổi bật
Bài viết nổi bật