Thuật toán tìm kiếm nhị phân là gì? Cách hoạt động và ứng dụng với cây nhị phân tìm kiếm

Trong lập trình và khoa học máy tính, tìm kiếm là một trong những thao tác cơ bản nhất. Khi làm việc với hàng nghìn, hàng triệu hay thậm chí hàng tỷ phần tử dữ liệu, việc lựa chọn một phương pháp tìm kiếm hiệu quả có thể tạo ra sự khác biệt rất lớn về tốc độ xử lý. Một trong những thuật toán nổi tiếng và được sử dụng phổ biến nhất là thuật toán tìm kiếm nhị phân.

Vậy thuật toán tìm kiếm nhị phân là gì, hoạt động như thế nào và có liên quan gì đến cây nhị phân tìm kiếm? Hãy cùng tìm hiểu chi tiết trong bài viết dưới đây.

Thuật toán tìm kiếm nhị phân là gì?

Thuật toán tìm kiếm nhị phân hay Binary Search là thuật toán dùng để tìm kiếm một phần tử trong một tập dữ liệu đã được sắp xếp.

Thay vì kiểm tra từng phần tử từ đầu đến cuối như tìm kiếm tuyến tính, thuật toán tìm kiếm nhị phân liên tục chia phạm vi tìm kiếm thành hai phần.

Ý tưởng chính rất đơn giản

Xác định phần tử nằm ở giữa danh sách.
So sánh phần tử cần tìm với phần tử ở giữa.
Nếu bằng nhau, quá trình tìm kiếm kết thúc.
Nếu giá trị cần tìm nhỏ hơn chỉ tiếp tục tìm ở nửa bên trái.
Nếu lớn hơn chỉ tiếp tục tìm ở nửa bên phải.

Quá trình này được lặp lại cho đến khi tìm thấy phần tử hoặc phạm vi tìm kiếm không còn phần tử nào.

Điểm quan trọng nhất cần nhớ là thuật toán tìm kiếm nhị phân chỉ hoạt động hiệu quả khi dữ liệu đã được sắp xếp.

Ví dụ về thuật toán tìm kiếm nhị phân

Giả sử ta có dãy số đã sắp xếp

2, 5, 8, 12, 16, 23, 38, 56, 72, 91

Yêu cầu tìm số 23.

Đầu tiên thuật toán sẽ kiểm tra phần tử ở giữa. Giả sử phần tử giữa là 16.

Ta có

23 > 16

Điều này có nghĩa rằng 23 chắc chắn không nằm ở nửa bên trái. Thuật toán sẽ loại bỏ toàn bộ phần dữ liệu từ 2 đến 16 và chỉ tìm kiếm trong

23, 38, 56, 72, 91

Tiếp tục lấy phần tử giữa giả sử là 56.

Ta có

23 < 56

Lúc này thuật toán loại bỏ nửa bên phải và tiếp tục tìm trong

23, 38

Sau một vài bước tiếp theo, số 23 sẽ được tìm thấy.

Thay vì kiểm tra lần lượt 2, 5, 8, 12, 16 rồi mới đến 23 thì Binary Search liên tục loại bỏ một nửa số phần tử không cần thiết.

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

Để hiểu rõ hơn thuật toán tìm kiếm nhị phân là gì ta có thể mô tả quá trình bằng ba biến cơ bản

left vị trí đầu của phạm vi tìm kiếm.
right vị trí cuối của phạm vi tìm kiếm.
mid vị trí ở giữa.

Công thức thường dùng để xác định vị trí giữa là

mid = left + (right – left) / 2

Sau đó so sánh phần tử tại vị trí mid với giá trị cần tìm.

Có ba trường hợp xảy ra

Nếu array[mid] bằng giá trị cần tìm, thuật toán trả về vị trí mid.
Nếu array[mid] lớn hơn giá trị cần tìm, cập nhật right = mid - 1.
Nếu array[mid] nhỏ hơn giá trị cần tìm, cập nhật left = mid + 1.

Quá trình tiếp tục khi left <= right.

Nếu điều kiện này không còn đúng mà vẫn chưa tìm thấy phần tử có thể kết luận giá trị cần tìm không tồn tại trong danh sách.

Độ phức tạp của thuật toán tìm kiếm nhị phân

Một trong những lý do khiến thuật toán tìm kiếm nhị phân được sử dụng rộng rãi là tốc độ rất nhanh.

Độ phức tạp thời gian của Binary Search là

O(log n)

Trong đó n là số lượng phần tử trong tập dữ liệu.

Điều này có nghĩa là mỗi lần thực hiện, thuật toán giảm một nửa phạm vi cần tìm.

Ví dụ với khoảng 1.000 phần tử, Binary Search chỉ cần tối đa khoảng 10 lần so sánh.

Với 1.000.000 phần tử, số lần so sánh tối đa chỉ khoảng 20.

Trong khi đó, thuật toán tìm kiếm tuyến tính trong trường hợp xấu nhất có thể phải kiểm tra toàn bộ 1.000.000 phần tử.

Đây chính là lợi thế lớn nhất của thuật toán tìm kiếm nhị phân.

Ưu điểm của thuật toán tìm kiếm nhị phân

Binary Search có nhiều ưu điểm đáng chú ý.

Trước hết, thuật toán có tốc độ tìm kiếm nhanh đối với tập dữ liệu lớn nhờ việc loại bỏ một nửa phạm vi sau mỗi bước cho nên số lần so sánh giảm đáng kể.

Ngoài ra, thuật toán tương đối đơn giản, dễ cài đặt bằng cả vòng lặp và đệ quy.

Thuật toán tìm kiếm nhị phân cũng là nền tảng của nhiều kỹ thuật nâng cao trong lập trình chẳng hạn như tìm vị trí chèn phần tử, tìm giới hạn dưới và giới hạn trên hay giải các bài toán tối ưu bằng phương pháp binary search on answer.

Hạn chế của thuật toán tìm kiếm nhị phân

Mặc dù có hiệu suất tốt nhưng Binary Search cũng có một số hạn chế.

Điều kiện quan trọng nhất là dữ liệu phải được sắp xếp. Nếu danh sách chưa được sắp xếp thì ta cần sắp xếp trước khi áp dụng thuật toán.

Ngoài ra, Binary Search hoạt động thuận lợi nhất trên các cấu trúc dữ liệu cho phép truy cập trực tiếp đến phần tử theo chỉ số chẳng hạn như mảng.

Với một số cấu trúc như danh sách liên kết, việc truy cập phần tử ở giữa không nhanh nên thuật toán có thể mất đi lợi thế.

Cây nhị phân tìm kiếm là gì?

Bên cạnh thuật toán tìm kiếm nhị phân, một khái niệm rất thường gặp khác là cây nhị phân tìm kiếm hay Binary Search Tree viết tắt là BST.

Cây nhị phân tìm kiếm là một dạng cây nhị phân có quy tắc đặc biệt

Mỗi nút có tối đa hai nút con.
Tất cả giá trị ở cây con bên trái nhỏ hơn giá trị của nút hiện tại.
Tất cả giá trị ở cây con bên phải lớn hơn giá trị của nút hiện tại.

Ví dụ với nút gốc là 50

Các giá trị nhỏ hơn 50 sẽ nằm về phía bên trái.
Các giá trị lớn hơn 50 sẽ nằm về phía bên phải.

Nhờ quy tắc này, quá trình tìm kiếm trong cây có cách hoạt động tương tự Binary Search.

Tìm kiếm trong cây nhị phân tìm kiếm

Giả sử cần tìm giá trị 70 trong một cây nhị phân tìm kiếm.

Ta bắt đầu từ nút gốc.

Nếu nút gốc có giá trị 50 thì

70 > 50

Do đó, ta không cần kiểm tra cây con bên trái mà chuyển thẳng sang cây con bên phải.

Nếu nút tiếp theo có giá trị 80 thì

70 < 80

Ta tiếp tục chuyển sang cây con bên trái của 80.

Quá trình này tiếp tục cho đến khi tìm thấy 70 hoặc gặp một nút rỗng.

Cơ chế này rất giống với thuật toán tìm kiếm nhị phân trên mảng đã sắp xếp ở mỗi bước, thuật toán loại bỏ một phần dữ liệu không cần kiểm tra.

Sự khác nhau giữa thuật toán tìm kiếm nhị phân và cây nhị phân tìm kiếm

Mặc dù có tên gần giống nhau, thuật toán tìm kiếm nhị phân và cây nhị phân tìm kiếm không phải là cùng một khái niệm.

Thuật toán tìm kiếm nhị phân là một phương pháp tìm kiếm thường được áp dụng trên mảng hoặc danh sách đã sắp xếp.

Trong khi đó, cây nhị phân tìm kiếm là một cấu trúc dữ liệu dùng để tổ chức và lưu trữ dữ liệu.

Binary Search thường yêu cầu dữ liệu đã được sắp xếp sẵn. Còn BST duy trì trật tự dữ liệu ngay trong cấu trúc của cây.

Một cây nhị phân tìm kiếm cân bằng có thể thực hiện thao tác tìm kiếm, thêm cả xóa phần tử với độ phức tạp trung bình khoảng

O(log n)

Tuy nhiên nếu cây bị lệch nghiêm trọng thì độ phức tạp trong trường hợp xấu nhất có thể trở thành O(n).

Ứng dụng của thuật toán tìm kiếm nhị phân

Thuật toán tìm kiếm nhị phân không chỉ dùng tìm một con số trong một mảng.

Trong thực tế, Binary Search có thể được sử dụng trong nhiều bài toán như

Tìm kiếm dữ liệu trong danh sách đã sắp xếp.
Tìm vị trí đầu tiên hoặc cuối cùng của một giá trị.
Tìm phần tử gần nhất với giá trị cần tìm.
Xác định vị trí chèn một phần tử mà vẫn giữ nguyên thứ tự.
Tối ưu hóa một giá trị thỏa mãn điều kiện nào đó.
Tìm kiếm trong các hệ thống dữ liệu lớn.
Làm nền tảng cho nhiều bài toán thi thuật toán và lập trình.

Đặc biệt, kỹ thuật Binary Search còn được mở rộng sang dạng tìm kiếm nhị phân trên đáp án. Khi đó ta không tìm một phần tử cụ thể mà tìm giá trị nhỏ nhất hoặc lớn nhất thỏa mãn một điều kiện.

Hiểu rõ thuật toán tìm kiếm nhị phân là gì là kiến thức nền tảng quan trọng đối với bất kỳ ai học lập trình và cấu trúc dữ liệu. Với độ phức tạp O(log n), Binary Search giúp tìm kiếm dữ liệu nhanh hơn rất nhiều so với phương pháp duyệt tuần tự khi làm việc với tập dữ liệu đã được sắp xếp.

Bên cạnh đó, cây nhị phân tìm kiếm là một cấu trúc dữ liệu có nguyên lý tương tự cho phép tổ chức dữ liệu theo thứ tự để hỗ trợ các thao tác tìm kiếm, thêm và xóa hiệu quả.

Khi học thuật toán bạn nên nắm chắc cách Binary Search chia đôi phạm vi tìm kiếm, điều kiện để áp dụng và sự khác biệt giữa thuật toán này với Binary Search Tree sẽ là nền tảng hữu ích để tiếp tục tìm hiểu các chủ đề nâng cao hơn như cây AVL, cây đỏ-đen, tìm kiếm nhị phân trên đáp án và các thuật toán tối ưu khác.