Cộng đồng chia sẻ tri thức Lib24.vn

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

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 11:00:21


Mục lục
* * * * *

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 phân chia và chinh phục. Để thuật toán này hoạt động chính xác, 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ặt hàng cụ thể bằng cách so sánh hầu hết các mặt hàng ở giữa của bộ sưu tập. Nếu một trận đấu 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 trong mảng con ở bên phải của mục giữa. Quá trình này tiếp tục trên mảng con cho đến khi kích thước của phân đoạn 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 đí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 tôi so sánh giá trị được lưu trữ tại vị trí 4, với giá trị đượ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 khớp. Vì giá trị lớn hơn 27 và chúng tôi có một mảng được sắp xếp, vì vậy chúng tôi 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 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 tôi là 7 bây giờ. 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 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.

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ị đí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ã giả

Mã giả của 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

Được cập nhật: hôm kia lúc 23:54:18 | Lượt xem: 739