Thuật toán Tìm kiếm nhị phân (Binary Search)

Tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm nhanh với độ phức tạp trong thời gian chạy là Ο(log n). Thuật toán tìm kiếm này hoạt động theo nguyên tắc chia để trị. Để thuật toán này có thể hoạt động bình thường, việc thu thập dữ liệu phải ở dạng đã được sắp xếp.

Binary Search tìm kiếm một mục cụ thể bằng cách so sánh mục ở giữa nhất của bộ sưu tập. Nếu khớp xảy ra, thì chỉ mục của mục được trả về. Nếu mục ở giữa lớn hơn mục, thì mục đó được tìm kiếm trong mảng con bên trái của mục ở giữa. Mặt khác, mục được tìm kiếm sẽ nằm trong mảng phụ ở bên phải của mục ở giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống bằng không.

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 mục tiêu. 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 đã sắp xếp của chúng ta và giả sử rằng chúng ta 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ị được lưu trữ tại vị trí 4, với giá trị đang được tìm kiếm, tức là 31. Chúng ta thấy rằng giá trị tại vị trí 4 là 27, giá trị này không khớp. Vì giá trị lớn hơn 27 và chúng ta có một mảng được sắp xếp, nên chúng ta cũng biết rằng giá trị đích phải nằm ở phần trên của mảng.

Chúng ta thay đổi mức thấp thành mức trung bình + 1 và tìm lại giá trị mức trung bình mới.

low = mid + 1
mid = low + (high - low) / 2

Trung bình mới của chúng ta bây giờ là 7. Ta so sánh giá trị được lưu trữ tại vị trí 7 với giá trị mục tiêu 31.

Giá trị được lưu trữ tại vị trí 7 không khớp, thay vào đó, nó lớn hơn mục tiêu tìm kiếm. Vì vậy, giá trị phải ở phần dưới từ vị trí này.

Do đó, ta tính toán lại giữa. Lần này là 5.

So sánh giá trị được lưu trữ tại vị trí 5 với giá trị mục tiêu. Ta thấy trùng khớp.

Chúng ta kết luận rằng giá trị mục tiêu 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ần so sánh được thực hiện với số lượng rất ít.

Pseudocode

Pseudocode của thuật toán binary search trông sẽ như thế này:

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

Nếu bạn muốn hiểu sâu hơn về Binary Search, đăng ký ngay lớp học thuật toán FSE Big Tech – học trực tiếp từ giảng viên hiện đang làm việc tại các công ty hàng đầu như Google, Amazon, TikTok, Booking, Grab!