Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Tìm kiếm nhị phân trong Java, 3 cách cài đặt Binary Search đơn giản
Tìm hiểu thuật toán tìm kiếm nhị phân trong Java. Đây là một thuật toán cơ bản trong kỹ thuật lập trình, để giúp bạn hiểu và áp dụng được vào các bài toán thì hôm nay freetuts sẽ phân tích và triển khai thuật toán tìm kiếm nhị phân từ cơ bản đến nâng cao.
Ở bài trước, freetuts đã hướng dẫn các bạn cách tiếp cận cũng như cách sử dụng thuật toán tìm kiếm tuyến tính (linear search) trong Java một cách hiệu quả nhất. Trong bài này, chúng ta sẽ tiếp tục chương thuật toán tìm kiếm và sắp xếp bằng việc tìm hiểu về thuật toán tìm kiếm nhị phân (binary search) trong Java.
Giải thuật tìm kiếm nhị phân trong Java
Tìm kiếm nhị phân trong Java là một thuật toán tìm kiếm để tìm vị trí của một phần tử trong một mảng được sắp xếp tăng dần.Trong cách tiếp cận này, phần tử luôn được tìm kiếm ở giữa một phần của mảng.
Lưu ý: Nếu mảng chưa được sắp xếp thì chúng ta sử dụng phương thức Arrays.sort(arr).
Bài viết này được đăng tại [free tuts .net]
Các bước cơ bản của thuật toán tìm kiếm nhị phân trong Java:
- Bước 1: Sắp xếp mảng: Thuật toán tìm kiếm nhị phân yêu cầu mảng được sắp xếp tăng dần hoặc giảm dần. Nếu mảng chưa được sắp xếp, ta cần sắp xếp trước đó, sử dụng phương thức
Arrays.sort(arr) - Bước 2: Khởi tạo giá trị
lowvàhigh: Khởi tạo giá trịlowlà chỉ số đầu tiên của mảng vàhighlà chỉ số cuối cùng của mảng. - Bước 3: Tìm giá trị
mid: Tính toán giá trị trung bình củalowvàhighđể tìm vị trímidtrong mảng. - Bước 4: So sánh giá trị tại
midvới giá trị cần tìm kiếm:- Nếu giá trị tại vị trí
midbằng với giá trị cần tìm kiếm, trả vềmid. - Nếu giá trị tại
midnhỏ hơn giá trị cần tìm kiếm, chuyểnlowsangmid + 1để tìm kiếm trong nửa phía sau của mảng. - Nếu giá trị tại
midlớn hơn giá trị cần tìm kiếm, chuyểnhighsangmid - 1để tìm kiếm trong nửa phía trước của mảng.
- Nếu giá trị tại vị trí
- Bước 5: Lặp lại quá trình tìm kiếm: Lặp lại các bước 3 và 4 cho đến khi tìm thấy giá trị cần tìm hoặc không còn phần tử nào để xem xét.
- Bước 6: Trả về kết quả: Nếu tìm thấy giá trị cần tìm, trả về chỉ số của phần tử tương ứng trong mảng. Nếu không tìm thấy, trả về một giá trị đại diện cho việc không tìm thấy (thường là -1).
Hãy xem một ví dụ về tìm kiếm nhị phân trong Java mà freetuts triển khai dưới đây để xem cách chúng ta sẽ tìm kiếm một phần tử trong một mảng như thế nào nhé.
Thuật toán tìm kiếm nhị phân cơ bản trong Java
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
public class BinarySearch {
public static int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // không tìm thấy giá trị cần tìm trong mảng
}
public static void main(String[] args) {
int[] arr = { 1, 3, 4, 6, 8, 9, 11, 12, 15, 17 };
int key = 9;
int index = binarySearch(arr, key);
System.out.println("Học lập trình Java free tại freetuts.net");
if (index == -1) {
System.out.println("Không tìm thấy " + key + " trong mảng.");
} else {
System.out.println(key + " được tìm thấy tại chỉ số " + index + " trong mảng.");
}
}
}
Kết quả:
Thuật toán tìm kiếm tuyến tính trong Java tại freetuts! 9 được tìm thấy tại chỉ số 5 trong mảng
Trên đây là một bài tìm kiếm cơ bản áp dụng thuật toán tìm kiếm nhị phân trong Java. Các bạn hãy thử triển khai một bài tìm kiếm dựa vào thuật toán tìm kiếm nhị phân trong Java để hiểu hơn về thuật toán này nhé.
Thuật toán tìm kiếm nhị phân trong Java sử dụng đệ quy
Tiếp theo chúng ta đến với một cách triển khai khác của thuật toán tìm kiếm nhị phân trong Java bằng cách sử dụng phương pháp Đệ quy (Recursion).
Giải thích đệ quy: Đệ quy là một khái niệm trong lập trình, trong đó một hàm có thể gọi chính nó để giải quyết một bài toán lớn hơn bằng cách giải quyết nhiều bài toán nhỏ hơn. Nó cho phép chúng ta giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán nhỏ hơn và xử lý chúng đơn giản hơn.
Đây là đoạn code ví dụ minh họa cho thuật toán tìm kiếm nhị phân bằng đệ quy trong Java:
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
public class BinarySearchRecursive {
public static int binarySearch(int[] arr, int key, int low, int high) {
if (low > high) {
return -1; // không tìm thấy giá trị cần tìm trong mảng
}
int mid = (low + high) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
return binarySearch(arr, key, mid + 1, high);
} else {
return binarySearch(arr, key, low, mid - 1);
}
}
public static void main(String[] args) {
int[] arr = { 1, 3, 4, 6, 8, 9, 11, 12, 15, 17 };
int key = 9;
int index = binarySearch(arr, key, 0, arr.length - 1);
System.out.println("Học lập trình Java miễn phí tại freetuts.net");
if (index == -1) {
System.out.println("Không tìm thấy " + key + " trong mảng.");
} else {
System.out.println(key + " được tìm thấy tại chỉ số " + index + " trong mảng.");
}
}
}
Giải thích code:
Chương trình tương tự như thuật toán tìm kiếm nhị phân bằng vòng lặp, tuy nhiên ở đây, chúng ta sử dụng đệ quy để thay thế cho vòng lặp.
- Nếu
low > high, chúng ta trả về giá trị -1 - Nếu low < high chúng ta tính toán chỉ số
midvà so sánh giá trị tại chỉ số này với giá trị cần tìm.- Nếu bằng nhau, chúng ta trả về chỉ số
mid - Nếu giá trị tại chỉ số
midnhỏ hơn giá trị cần tìm, chúng ta gọi đệ quy trên phần mảng bên phải củamid. - Ngược lại chúng ta gọi đệ quy trên phần mảng bên trái của
mid.
- Nếu bằng nhau, chúng ta trả về chỉ số
Kết quả:
Học lập trình Java miễn phí tại freetuts.net! 9 được tìm thấy tại chỉ số 5 trong mảng
Trên đây là một bài tìm kiếm sử dụng đệ quy để triển khai thuật toán tìm kiếm nhị phân trong Java, thông qua bài này giúp các bạn hiểu được cách triển khai thuật toán tìm kiếm bằng phương pháp đệ quy - một phương pháp hay, thường được áp dụng trong lập trình các bài toán lớn.
Thuật toán tìm kiếm nhị phân trong Java sử dụng Arrays.binarySearch()
Ngoài hai cách triển khai trên thì trong mảng cũng có một phương thức giúp chúng ta sử dụng thuật toán tìm kiếm nhị phân sử một cách nhanh nhất. Đó là phương thức Arrays.binarySearch()
Dưới đây là đoạn code minh họa sử dụng Arrays.binarySearch() trong việc triển khai thuật toán tìm kiếm nhị phân trong Java. Mời các bạn tham khảo.
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
import java.util.Arrays;
class BinarySearchExample2{
public static void main(String args[]){
int arr[] = { 1, 3, 4, 6, 8, 9, 11, 12, 15, 17 };
int key = 9;
int result = Arrays.binarySearch(arr,key);
System.out.println("Học lập trình Java miễn phí tại freetuts.net");
if (result < 0) {
System.out.println("Không tìm thấy " + key + " trong mảng.");
} else {
System.out.println(key + " được tìm thấy tại chỉ số " + result + " trong mảng.");
}
}
} Kết quả:
Học lập trình Java miễn phí tại freetuts.net! 9 được tìm thấy tại chỉ số 5 trong mảng
Qua đoạn code trên, freetuts đã cung cấp cách triển khai thuật toán tìm kiếm nhị phân trong Java một cách nhanh nhất bằng cách sử dụng phương thức Arrays.binarySearch(arr).
Tổng Kết
Trong bài viết này, với thuật toán tìm kiếm nhị phân kinh điển trong Java, freetuts đã giới thiệu cho các bạn 3 cách triển khai để có thể hiểu và áp dụng một cách thuần thục nhất:
- Thuật toán tìm kiếm nhị phân cơ bản trong Java
- Thuật toán tìm kiếm nhị phân trong Java sử dụng đệ quy
- Thuật toán tìm kiếm nhị phân trong Java sử dụng phương thức
Arrays.binarySearch
Chúc các bạn thực hiện thành công code của mình.
Ở bài tiếp theo trong chương này, freetuts sẽ giới thiệu thuật toán Sắp xếp nổi bọt (Bubble Sort) trong Java. Mời các bạn đón đọc!
