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 thông qua các mục như con người làm. Trong khi con người có thể thay đổi cách tiếp cận để tìm kiếm thứ gì đó, thì máy tính cần được cung cấp các hướng dẫn cụ thể về cách xác định vị trí một vật cụ thể. Đó là nơi các thuật toán tiêu chuẩn hữu ích.
Các tìm kiếm nhị phân là một ví dụ của một thuật toán tiêu chuẩn. Chúng được sử dụng để tìm một phần tử trong một mảng các mục đã được 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ẽ xem xét hai ví dụ về tìm kiếm nhị phân:một sử dụng phương pháp đệ quy và một sử dụng phương pháp lặp lại.
Hãy bắt đầu!
Tìm kiếm nhị phân là gì?
Tìm kiếm nhị phân là một thuật toán tìm kiếm xác định vị trí của một phần tử trong một mảng được sắp xếp.
Tìm kiếm nhị phân bắt đầu bằng cách chia một nửa danh sách. Sau đó, tìm kiếm sẽ so sánh số ở giữa với số mà thuật toán đang tìm kiếm.
Nếu số nhỏ hơn số ở giữa, quá trình này được lặp lại cho nửa dưới của danh sách; nếu không, quá trình này được 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, một kiểu tìm kiếm phổ biến khác. Điều này là do mỗi lần thuật toán tìm kiếm một mục, nó sẽ giảm số lượng mục cần tìm kiếm xuống một hệ số là hai.
Tìm kiếm nhị phân chỉ có thể được thực hiện trên một danh sách các mục đã được sắp xếp. Điều này có nghĩa là nếu bạn chưa có danh sách được sắp xếp, bạn sẽ cần phải sắp xếp nó bằng thuật toán sắp xếp trước khi chạy tìm kiếm nhị phân.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Tìm kiếm nhị phân hoạt động như thế nào?
Tìm kiếm nhị phân có thể được thực hiện theo hai cách:lặp đi lặp lại hoặc đệ quy.
Tìm kiếm nhị phân lặp lại là một trong đó các vòng lặp được sử dụng để tìm kiếm một mục trong danh sách. Tìm kiếm nhị phân đệ quy sử dụng một hàm gọi đi gọi lại chính nó để tìm một mục trong danh sách. Tìm kiếm nhị phân đệ quy sử dụng cách tiếp cận chia và chinh phục để tìm một mục.
Bạn có thể tìm hiểu thêm về đệ quy trong hướng dẫn của chúng tôi về đệ quy Java.
Thuật toán chung để thực hiện tìm kiếm nhị phân là giống nhau cho dù bạn quyết định sử dụng cách tiếp cận nào.
Hãy xem xét danh sách sau:
| 6 | 7 | 8 | 9 | 10 |
Chúng tôi sẽ tìm kiếm số 7 trong danh sách của chúng tôi. Để bắt đầu, chúng ta sẽ đặt hai con trỏ đại diện cho các vị trí thấp nhất và cao nhất trong danh sách của chúng ta:
| Low | | | | Cao |
| 6 | 7 | 8 | 9 | 10 |
Tiếp theo, chúng ta phải tìm phần tử ở giữa trong mảng của chúng ta. Chúng ta có thể làm điều này bằng cách sử dụng công thức:(thấp + cao) / 2. Trong trường hợp này, phần tử ở giữa là 8.
Thuật toán của chúng tôi sẽ so sánh xem phần tử ở giữa có bằng phần tử mà chúng tôi đang tìm kiếm hay không. Nếu các con số bằng nhau, việc tìm kiếm của chúng tôi có thể dừng lại. Chúng tôi đang tìm số 7, không bằng 8, vì vậy việc tìm kiếm của chúng tôi vẫn tiếp tục.
Thuật toán của chúng tôi so sánh liệu số mà chúng tôi đang tìm kiếm có lớn hơn số ở giữa hay không. Nếu nó lớn hơn, việc tìm kiếm của chúng tôi sẽ bắt đầu lại từ nửa trên cùng của danh sách. Điều này được thực hiện bằng cách đặt thấp bằng low =middle_number + 1. Nếu không, tìm kiếm sẽ bắt đầu lại ở nửa cuối danh sách của chúng tôi.
7 (số chúng tôi đang tìm kiếm) không lớn hơn 8 (số ở giữa). Điều này có nghĩa là thuật toán của chúng tôi sẽ tìm kiếm qua nửa cuối danh sách của chúng tôi. Chúng tôi thực hiện điều này bằng cách đặt giá trị “cao” của mình thành high =middle_number - 1.
| Low | Giữa | Cao | | |
| 6 | 7 | 8 | 9 | 10 |
Bây giờ, thuật toán của chúng tôi sẽ lặp lại tìm kiếm của chúng tôi. Chúng tôi sẽ so sánh số giữa, 7, với số mà chúng tôi đang tìm kiếm. Chúng tôi đang tìm số 7, vì vậy thuật toán tìm kiếm của chúng tôi dừng lại. Chúng tôi đã tìm thấy vị trí thứ 7 trong danh sách của mình!
Cách triển khai tìm kiếm nhị phân trong Java
Chúng tôi đã hoàn thành lý thuyết nên bây giờ tất cả những gì còn lại cần làm là triển khai tìm kiếm của chúng tôi. Đó là một việc chúng ta phải trải qua và tìm kiếm danh sách; hoàn toàn là một việc khác là viết mã một thuật toán thực hiện tìm kiếm cho chúng tôi.
Chúng ta sẽ bắt đầu bằng cách viết một chương trình triển khai tìm kiếm nhị phân Java bằng phương pháp lặp lại.
Phương pháp lặp lại
Hãy xác định một hàm có tên là searchItems , tìm kiếm trong danh sách các mục của chúng tôi:
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 thông qua danh sách các mục của chúng tôi bằng cách sử dụng tìm kiếm nhị phân.
Hàm của chúng ta chấp nhận bốn tham số:danh sách mà chúng ta muốn tìm kiếm (mảng), mục chúng ta đang tìm kiếm (seekFor), số thấp (low) và số cao (cao).
Bên trong hàm của chúng ta, chúng ta đã khai báo một vòng lặp while. Trong khi giá trị của "thấp" nhỏ hơn hoặc bằng "cao", vòng lặp sẽ thực hiện.
Vòng lặp while của chúng tôi bắt đầu bằng cách tính số ở giữa. Sau đó, nó sẽ kiểm tra xem liệu giá trị tại vị trí đó có bằng với giá trị mà chúng ta đang tìm kiếm hay không.
Nếu các số đó bằng nhau, giá trị đó được trả về chương trình chính của chúng ta. Nếu không, chương trình của chúng tôi sẽ kiểm tra xem giá trị ở vị trí giữa có nhỏ hơn giá trị mà chúng tôi đang tìm kiếm hay không. Nếu đúng, một giá trị thấp mới được đặt.
Nếu không, một giá trị cao mới được đặt để danh sách của chúng tôi có thể tìm kiếm lại ở nửa trên của danh sách.
Nếu mục của chúng tôi không được tìm thấy, -1 được trả lại. Chúng tôi sẽ sử dụng điều này để nói với chương trình chính của chúng tôi rằng không thể tìm thấy mục danh sách trong một phút nữa.
Mã của chúng tôi chưa thực hiện được gì vì chúng tôi chưa viết chương trình chính của mình. Thêm mã sau vào bên dưới searchItems() chức năng trong lớp Tìm kiếm nhị phân của bạn:
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ã của chúng tôi và xem điều gì sẽ xảy ra:
7 was found at index position 1. We've found the position of our number!
Chương trình chính của chúng ta bắt đầu bằng cách khởi tạo một phiên bản của lớp BinarySearch. Chúng tôi sử dụng điều này để bắt đầu thời gian chờ tìm kiếm của chúng tôi trong chương trình. Sau đó, chúng tôi xác định ba biến:
- listToSearch:Danh sách mà chúng tôi muốn tìm kiếm.
- listLength:Độ dài của danh sách.
- numberToFind:Số mà chúng tôi đang tìm kiếm trong danh sách.
Khi chúng tôi đã xác định các biến này, chúng tôi sử dụng searchItems() mà chúng tôi đã khai báo trước đó để tìm một số trong danh sách của chúng tôi. Chúng tôi gán giá trị mà hàm này trả về cho biến “findNumber”.
Nếu findNumber không bằng -1 - có nghĩa là số của chúng tôi đã được tìm thấy - thì vị trí chỉ mục của mục mà chúng tôi đang tìm kiếm sẽ được in ra bảng điều khiển. Nếu không, một thông báo được in ra bảng điều khiển cho chúng tôi biết số điện thoại không được tìm thấy.
Phương pháp đệ quy
Một cách tiếp cận đệ quy có thể được thực hiện để thực hiện tìm kiếm nhị phân. Đây là nơi bạn viết một hàm gọi chính nó cho đến khi tìm thấy một mục cụ thể.
Hãy bắt đầu bằng cách xác định một hàm thực hiện tìm kiếm đệ quy nhị phân của chúng ta:
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 thực hiện tìm kiếm nhị phân của chúng tôi theo một cách khác. Thay vì sử dụng vòng lặp while, chúng tôi sử dụng if để kiểm tra xem số cao bằng hoặc nhỏ hơn số thấp.
Nếu câu lệnh này đánh giá là true, quá trình tìm kiếm của chúng tôi sẽ bắt đầu. Nếu không, -1 được trả về, điều này cho chương trình của chúng tôi biết rằng không thể tìm thấy một mục cụ thể trong danh sách.
Bên trong if của chúng tôi , chúng tôi kiểm tra xem giá trị của số ở giữa có bằng với số mà chúng tôi đang tìm kiếm hay không. Nếu đúng, chúng tôi trả lại số đó cho chương trình chính của chúng tôi.
Nếu câu lệnh này không đánh giá là true, chương trình của chúng tôi sẽ kiểm tra xem liệu số ở vị trí giữa có nhỏ hơn số mà chúng tôi đang tìm kiếm hay không. Nếu đúng như vậy, searchItems() phương thức sẽ được chạy lại, nhưng lần này số thấp của chúng ta sẽ bằng một lớn hơn số giữa của chúng ta. Điều này chia số mục mà danh sách của chúng tôi cần tìm kiếm cho hai.
Nếu không, searchItems() được chạy lại và giá trị của số cao nhất được thực hiện bằng số ở giữa trừ đi một. Điều này có nghĩa là chúng tôi chỉ có thể tinh chỉnh tìm kiếm của mình ở nửa bên trái của danh sách.
Chúng ta có thể sử dụng cùng một hàm chính mà chúng ta đã viết trước đó để kiểm tra mã của chúng ta. Hãy xem điều gì sẽ xảy ra khi chúng tôi chạy mã của mình:
7 was found at index position 1.
Mục của chúng tôi đã được tìm thấy một lần nữa! Lần này, chúng tôi sử dụng phương pháp đệ quy để tìm số của chúng tôi thay vì số lặp lại.
Phân tích độ phức tạp
Thuật toán tìm kiếm nhị phân có độ phức tạp trường hợp tốt nhất là O (1). Điều này xảy ra khi mục đầu tiên được thuật toán so sánh là mục đang được tìm kiếm.
Thuật toán tìm kiếm nhị phân có độ phức tạp trung bình và trường hợp xấu nhất là O (log n). Điều này có nghĩa là, trong hầu hết các trường hợp và trong trường hợp xấu nhất, tốc độ của thuật toán chậm lại theo logarit tùy thuộc vào số lượng mục mà danh sách phải tìm kiếm.
Kết luận
Tìm kiếm nhị phân được sử dụng để tìm vị trí của một phần tử trong danh sách đã sắp xếp. Tìm kiếm nhị phân so sánh mục ở giữa một phần của mảng với số mà thuật toán đang tìm kiế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à do mỗi khi thực hiện tìm kiếm, số giá trị cần được tìm kiếm sẽ chia cho hai.
Bây giờ, bạn đã sẵn sàng triển khai tìm kiếm nhị phân trong Java như một lập trình viên chuyên nghiệp.