Tìm kiếm nhị phân (Binary Search) trong Java: Hướng dẫn chi tiết

Cách viết thuật toán Tìm kiếm nhị phân trong Java

Máy tính không tìm kiếm các mục như con người. Trong khi con người có thể thay đổi cách tiếp cận để tìm thứ gì đó, máy tính cần được cho hướng dẫn cụ thể về cách định vị mục cụ thể. Đó là nơi các thuật toán chuẩn có ích.

Tìm kiếm nhị phân là ví dụ của thuật toán chuẩn. Chúng được dùng để tìm phần tử trong mảng đã sắp xếp. Trong hướng dẫn này, chúng ta sẽ nói về tìm kiếm nhị phân là gì, cách chúng hoạt động, và cách bạn có thể triển khai chúng trong Java. Chúng ta sẽ đi qua hai ví dụ: một dùng cách đệ quy (recursive), một dùng cách lặp (iterative).

Hãy bắt đầu!

Tìm kiếm nhị phân (Binary Search) là gì?

Tìm kiếm nhị phân là thuật toán tìm kiếm định vị vị trí phần tử trong mảng đã sắp xếp.

Tìm kiếm nhị phân bắt đầu bằng chia danh sách làm đôi. Tìm kiếm sau đó so sánh số giữa với số mà thuật toán đang tìm.

Nếu số nhỏ hơn số giữa, quá trình này lặp lại cho nửa dưới của danh sách; ngược lại, quá trình lặp lại cho nửa trên của danh sách.

Tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính (linear search), một loại tìm kiếm phổ biến khác. Điều này là vì mỗi lần thuật toán tìm mục, nó giảm số mục cần tìm kiếm đi gấp đôi.

Tìm kiếm nhị phân chỉ có thể thực thi trên danh sách đã sắp xếp. Nghĩa là nếu bạn chưa có danh sách sắp xếp, bạn cần sắp xếp nó dùng thuật toán sắp xếp trước khi chạy tìm kiếm nhị phân.

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

Tìm kiếm nhị phân có thể triển khai theo hai cách: lặp (iterative) hoặc đệ quy (recursive).

Tìm kiếm nhị phân lặp là nơi dùng vòng lặp để tìm mục trong danh sách. Tìm kiếm nhị phân đệ quy dùng hàm gọi chính nó lại và lại để tìm mục. Tìm kiếm nhị phân đệ quy dùng cách chia để trị (divide and conquer) để tìm mục.

Bạn có thể tìm hiểu thêm về đệ quy trong hướng dẫn Java recursion của chúng tôi.

Thuật toán chung để triển khai tìm kiếm nhị phân là giống nhau bất kể cách bạn chọn.

Xem danh sách sau:

Chúng ta sẽ tìm số 7 trong danh sách. Để bắt đầu, chúng ta sẽ đặt hai con trỏ (pointers) đại diện cho vị trí thấp nhất và cao nhất trong danh sách:

Tiếp theo, chúng ta phải tìm phần tử giữa trong mảng. Chúng ta có thể làm bằng công thức: (low + high) / 2. Trong trường hợp này, phần tử giữa là 8.

Thuật toán sẽ so sánh xem phần tử giữa có bằng số chúng ta tìm không. Nếu các số bằng nhau, tìm kiếm có thể dừng. Chúng ta tìm số 7, không bằng 8, nên tìm kiếm tiếp tục.

Thuật toán so sánh xem số chúng ta tìm có lớn hơn số giữa không. Nếu lớn hơn, tìm kiếm sẽ bắt đầu lại trên nửa trên danh sách. Điều này thực hiện bằng cách đặt low = middle_number + 1. Ngược lại, tìm kiếm sẽ bắt đầu lại trên nửa dưới danh sách.

7 (số chúng ta tìm) không lớn hơn 8 (số giữa). Nghĩa là thuật toán sẽ tìm qua nửa dưới danh sách. Chúng ta làm bằng cách đặt giá trị "high" thành high = middle_number - 1.

Giờ thuật toán sẽ lặp lại tìm kiếm. Chúng ta so sánh số giữa, 7, với số chúng ta tìm. Chúng ta tìm số 7, nên thuật toán dừng. Chúng ta đã tìm thấy vị trí của 7 trong danh sách!

Cách triển khai Binary Search trong Java

Chúng ta xong lý thuyết nên giờ chỉ còn triển khai tìm kiếm. Việc tự tìm kiếm danh sách là một chuyện; viết thuật toán làm thay là chuyện khác hoàn toàn.

Chúng ta sẽ bắt đầu bằng viết chương trình triển khai binary search Java dùng phương pháp lặp.

Phương pháp lặp (Iterative Method)

Hãy định nghĩa hàm searchItems, tìm kiếm qua danh sách mục:

class BinarySearch { int searchItems(int array[], int searchingFor, int low, int high) { while (low <= high) { int middle = low + (high - low) / 2; if (array[middle] == searchingFor) { return middle; } else if (array[middle] < searchingFor) { low = middle + 1; } else { high = middle - 1; } } return -1; } }

Hàm này tìm kiếm qua danh sách dùng binary search.

Hàm chấp nhận bốn tham số: danh sách muốn tìm (array), mục đang tìm (searchingFor), số thấp (low), số cao (high).

Bên trong hàm chúng ta khai báo vòng lặp while. Trong khi giá trị "low" nhỏ hơn hoặc bằng "high", vòng lặp sẽ thực thi.

Vòng lặp while bắt đầu bằng tính số giữa. Sau đó kiểm tra xem giá trị tại vị trí đó có bằng số chúng ta tìm không.

Nếu các số bằng nhau, giá trị đó trả về chương trình chính. Nếu không, chương trình kiểm tra xem giá trị tại vị trí giữa có nhỏ hơn số chúng ta tìm không. Nếu có, giá trị low mới được đặt.

Ngược lại, giá trị high mới được đặt để danh sách có thể tìm lại trên nửa trên danh sách.

Nếu mục không tìm thấy, -1 được trả về. Chúng ta sẽ dùng này để báo cho chương trình chính biết mục danh sách không tìm thấy.

Mã chưa làm gì vì chưa viết chương trình chính. Thêm mã sau dưới hàm searchItems() trong lớp BinarySearch:

public static void main(String args[]) { BinarySearch newSearch = new BinarySearch(); int listToSearch[] = { 6, 7, 8, 9, 10 }; int listLength = listToSearch.length; int numberToFind = 7; int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1); if (findNumber != -1) { System.out.println(numberToFind + " was found at index position " + findNumber + "."); } else { System.out.println(numberToFind + " was not found in the list."); } }

Hãy chạy mã và xem gì xảy ra:

7 was found at index position 1. We've found the position of our number!

Chương trình chính bắt đầu bằng khởi tạo thể hiện của lớp BinarySearch. Chúng ta dùng này để bắt đầu tìm kiếm sau. Chúng ta định nghĩa ba biến:

• listToSearch: Danh sách muốn tìm qua.
• listLength: Độ dài danh sách.
• numberToFind: Số chúng ta tìm trong danh sách.

Khi đã định nghĩa xong các biến, chúng ta dùng hàm searchItems() khai báo trước để tìm số trong danh sách. Chúng ta gán giá trị hàm trả về cho biến "findNumber".

Nếu findNumber không bằng -1 – nghĩa là số đã tìm thấy – vị trí chỉ mục của mục đang tìm được in ra console. Ngược lại, thông báo in ra console báo số không tìm thấy.

Phương pháp đệ quy (Recursive Method)

Cách đệ quy có thể dùng để triển khai binary search. Đây là nơi viết hàm gọi chính nó cho đến khi tìm thấy mục chỉ định.

Hãy bắt đầu bằng định nghĩa hàm thực hiện binary search đệ quy:

class BinarySearch { int searchItems(int array[], int searchingFor, int low, int high) { if (high >= low) { int middle = low + (high - low) / 2; if (array[middle] == searchingFor) { return middle; } else if (array[middle] < searchingFor) { searchItems(array, searchingFor, middle + 1, high); } else { searchItems(array, searchingFor, low, middle - 1); } } return -1; } }

Hàm này triển khai binary search theo cách khác. Thay vì dùng vòng while, chúng ta dùng câu lệnh if kiểm tra xem số cao có bằng hoặc nhỏ hơn số thấp không.

Nếu câu lệnh đánh giá thành true, tìm kiếm bắt đầu. Ngược lại, -1 trả về, báo chương trình biết mục chỉ định không tìm thấy trong danh sách.

Bên trong câu lệnh if, chúng ta kiểm tra xem giá trị số giữa có bằng số chúng ta tìm không. Nếu có, trả về số đó cho chương trình chính.

Nếu câu lệnh không đánh giá thành true, chương trình kiểm tra xem số ở vị trí giữa có nhỏ hơn số chúng ta tìm không. Nếu có, phương thức searchItems() sẽ chạy lại, nhưng lần này low sẽ bằng một lớn hơn số giữa. Điều này chia số mục danh sách cần tìm kiếm đi đôi.

Ngược lại, searchItems() chạy lại và giá trị số cao nhất bằng số giữa trừ một. Nghĩa là chúng ta có thể tinh chỉnh tìm kiếm chỉ cho nửa trái danh sách.

Chúng ta có thể dùng cùng hàm chính viết trước để test mã. Hãy xem gì xảy ra khi chạy mã:

7 was found at index position 1.

Mục đã tìm thấy lại! Lần này, chúng ta dùng cách đệ quy để tìm số thay vì cách lặp.

Phân tích độ phức tạp (Complexity Analysis)

Thuật toán binary search có độ phức tạp trường hợp tốt nhất O(1). Điều này xảy ra khi mục đầu tiên được so sánh bởi thuật toán chính là mục đang tìm.

Thuật toán binary search có độ phức tạp trường hợp trung bình và xấu nhất O(log n). Nghĩa là, trong hầu hết trường hợp và trường hợp xấu nhất, tốc độ thuật toán chậm lại theo logarit tùy thuộc vào số mục danh sách cần tìm qua.

Kết luận

Tìm kiếm nhị phân dùng để tìm vị trí phần tử trong danh sách đã sắp xếp. Binary search so sánh mục ở giữa phần mảng với số mà thuật toán đang tìm.

Tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính. Điều này là vì mỗi lần tìm kiếm thực hiện, số giá trị cần tìm qua bị chia cho hai.

Bây giờ bạn đã sẵn sàng triển khai binary search trong Java như lập trình viên chuyên nghiệp.