Binary Search là gì? Cách thực hiện và ứng dụng của nó ra sao trong Java? Hãy theo dõi bài viết dưới đây để tìm ra câu trả lời nhé!

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

Thuật toán tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm tuyến tính cao cấp hơn với thời gian chạy là O(logN). Đối với các danh sách lớn, thuật toán này tốt hơn hẳn tìm kiếm tuyến tính, nhưng nó cũng đòi hỏi danh sách phải được sắp xếp từ trước và khả năng truy nhập ngẫu nhiên (random access).

Thuật toán tìm kiếm nhị phân thường được dùng để tìm kiếm các phần tử trong một danh sách đã được sắp xếp, ví dụ: Trong một danh bạ điện thoại sắp xếp theo tên, chúng ta có thể tìm kiếm số điện thoại của một người theo tên người đó.

Thuật toán tìm kiếm nhị phân có lợi thế lớn về độ phức tạp thời gian khi so sánh với các thuật toán tìm kiếm khác, thế nhưng chính nó cũng có một số nhược điểm. Đó chính là Thuật toán tìm kiếm nhị phân chậm hơn bảng băm.

Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân và thao tác này thường tốn thêm rất nhiều thời gian.

Ý tưởng và mô tả thuật toán tìm kiếm nhị phân

Vì thuật toán tìm kiếm nhị phân yêu cầu mảng đã được sắp xếp. Thế nên, đầu vào của chúng luôn là một mảng đã được sắp xếp. Do đó, thuật toán tìm kiếm nhị phân sẽ so sánh giá trị cần tìm với phần tử ở giữa của mảng (mảng được chia mảng ra làm 2 phần bên trái và bên phải phần tử đó).

Nếu chúng không bằng nhau thì dĩ nhiên một nửa không chứa mục tiêu sẽ bị bỏ đi. Và việc tìm kiếm tiếp tục ở nửa còn lại, một lần nữa lấy phần tử ở giữa được chọn để so sánh với giá trị đích và lặp lại điều này cho đến khi tìm thấy giá trị cần tìm. Nếu tìm kiếm kết thúc với nửa còn lại trống thì mục tiêu sẽ không nằm trong mảng.

Mặc dù ý tưởng rất đơn giản, nhưng việc thực hiện tìm kiếm nhị phân chính xác cần phải chú ý đến một số điểm quan trọng về điều kiện thoát và tính toán điểm giữa của nó. Về cơ bản, các bước thực hiện tìm kiếm nhị x trong mảng như sau:

• So sánh x với phần tử ở giữa.

• Nếu x khớp với phần tử ở giữa, chúng ta trả về chỉ số giữa (mid).

• Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa phân đoạn bên phải sau phần tử mid. Vì vậy, chúng ta chỉ tìm kiếm ở nửa phải của mảng.

• Nếu x nhỏ hơn phần tử giữa tiếp tục tìm ở nửa bên trái.

• Lặp lại đến khi tìm ra x hoặc trả về Null khi x không nằm trong mảng.

Ví dụ, chúng ta có mảng A[2, 4, 9, 10, 11, 22, 24, 31, 48, 56, 76, 86]

• Nhiệm vụ: Tìm vị trí của số 10 trong mảng

• Đầu tiên, ta so sánh số 10 với phần tử ở giữa thì thấy 10 < 22. Thế nên, hãy bỏ phần bên phải.

• Tiếp tục với phần bên trái với phần tử giữa là 9. Ta có 10 > 9. Vì thế ta bỏ phần bên trái.

• Tiếp tục với phần bên phải: So sánh phần tử ở giữa (với giữa = (chặn dưới + chặn trên)/2). Ta tìm thấy giá trị 10 ở vị trí 3.

Triển khai thuật toán tìm kiếm nhị phân trong Java

Từ ví dụ minh họa trên hình ở mục 2, chúng ta có thể triển khai Thuật toán tìm kiếm nhị phân trong chương trình trong Java như sau:

Chạy chương trình ta sẽ có được kết quả:

Phần tử được tìm thấy tại vị trí: 3

Binary Search – Thuật toán tìm kiếm nhị phân là thuật toán quan trọng và được ứng dụng nhiều trong việc lập trình. Việc các thuật toán kết hợp và bổ trợ cho nhau là điều không thể tránh khỏi, hi vọng qua bài viết trên, các bạn lập trình viên đã nắm được những kiến thức quan trọng về Binary Search và đã có thể áp dụng vào trong thực tế công việc.

Bộ môn Ứng dụng phần mềm
Cao đẳng FPT Mạng cá cược bóng đá Hà Nội