Cấu trúc dữ liệu và thuật toán Tìm kiếm nhị phân

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

Tìm kiếm nhị phân tìm kiếm một mục cụ thể bằng cách so sánh mục giữa hầu hết các bộ sưu tập. Nếu một trận đấu xảy ra, thì chỉ mục của mặt hàng đượ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. Nếu không, mục được tìm kiếm trong mảng con ở 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 0.

Tìm kiếm nhị phân hoạt động như thế nào?

Để tìm kiếm nhị phân hoạt động, mảng đích phải được sắp xếp. 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 tôi và 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 rồi, 0 + (9 - 0) / 2 = 4 (giá trị nguyên của 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 tôi thấy rằng giá trị tại vị trí 4 là 27, không phải là một kết quả khớp. Vì giá trị lớn hơn 27 và chúng ta có một mảng đã được sắp xếp, vì vậy 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 tôi thay đổi mức thấp thành giữa + 1 và tìm lại giá trị giữa mới.

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

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

Giá trị được lưu trữ tại vị trí 7 không phải là một sự trùng khớp, đúng hơn là giá trị mà chúng ta đang tìm kiếm. Vì vậy, giá trị phải ở phần dưới từ vị trí này.

Do đó, chúng tôi tính toán giữa một lần nữa. Lần này là 5.

Chúng tôi so sánh giá trị được lưu trữ tại vị trí 5 với giá trị mục tiêu của chúng tôi. Chúng tôi thấy rằng đó là một trận đấu.

Chúng tôi 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 làm giảm một nửa các mục có thể tìm kiếm và do đó giảm số lượng các phép so sánh được thực hiện thành các số rất ít.

Mã giả

Mã giả của các thuật toán tìm kiếm nhị phân sẽ trông 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

Để biết về cách triển khai tìm kiếm nhị phân sử dụng mảng trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .