Trong Java, có nhiều thuật toán tìm kiếm khác nhau, tùy thuộc vào yêu cầu cụ thể của bài toán. Dưới đây là một số thuật toán tìm kiếm phổ biến:
Tìm kiếm tuyến tính (Linear Search)
Thuật toán đơn giản, kiểm tra từng phần tử một để tìm kiếm giá trị cần. Đây không phải là thuật toán hiệu quả nếu danh sách lớn.
public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Trả về chỉ số của phần tử nếu tìm thấy
}
}
return -1; // Trả về -1 nếu không tìm thấy
}
}
Tìm kiếm nhị phân (Binary Search)
- Điều kiện: mảng đã được sắp xếp.
- Chia mảng làm hai và so sánh giá trị cần tìm với phần tử ở giữa để xác định xem nó ở nửa trái hay nửa phải.
- Tiếp tục quyết định tìm ở nửa nào cho đến khi tìm thấy giá trị hoặc mảng còn một phần tử.
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // Trả về chỉ số của phần tử nếu tìm thấy
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Trả về -1 nếu không tìm thấy
}
}
Lựa chọn giữa các thuật toán tìm kiếm phụ thuộc vào yêu cầu cụ thể của vấn đề và đặc tính của dữ liệu. Nếu danh sách đã được sắp xếp và ta có thể duy trì sự sắp xếp, Binary Search thường là lựa chọn tốt nhất. Tuy nhiên, nếu dữ liệu không được sắp xếp hoặc cần thêm, xóa các phần tử thường xuyên, Linear Search có thể là lựa chọn phù hợp hơn.