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 Thuật toán tìm kiếm nội suy trong Java (Interpolation Search)
Trong bài này freetuts sẽ giới thiệu thuật toán Interpolation Search (tìm kiếm nội suy). Đây là một trong những thuật toán tìm kiếm được sử dụng rất nhiều vì tốc độ tìm kiếm rất nhanh và chính xác.
Chúng ta sẽ cùng nhau tìm hiểu về Interpolation Search. Và so sánh nó với Binary Search, để xem sự khác biệt giữa hai cách tìm kiếm này. Sau đó mình sẽ đưa ra thuật toán cho phương pháp tìm kiếm này.
Thuật toán tìm kiếm nội suy trong Java
Thuật toán tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search. Nó có xu hướng tiến gần đến vị trí, giá trị tìm kiếm. Do đó tốc độ tìm kiếm được tối ưu rất cao và nhanh hơn nhiều so với Binary Search.
Cách thức hoạt động của nó dựa trên Binary Search, nhưng có sự cải tiến hơn. Đó chính là nó tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó để tìm.
Bài viết này được đăng tại [free tuts .net]
Ví dụ:
Chúng ta có danh sách các sinh viên trong một lớp. Nếu chúng ta muốn tìm một bạn tên Ý, thì chúng ta sẽ ưu tiên việc tìm kiếm từ cuối danh sách. Chứ không nên tìm kiếm từ đầu danh sách vì điều đó rất mất thời gian.
Với Interpolation Search nó sẽ linh hoạt hơn rất nhiều trong lúc tìm kiếm.
Các bước triển khai thuật toán tìm kiếm nội suy trong Java
- Bước 1: Xác định phần tử trung bình
Đầu tiên, ta cần xác định phần tử trung bình trong mảng. Phần tử này có thể được xác định bằng cách sử dụng công thức sau: mid = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]).
Trong đó, key là giá trị cần tìm, arr là mảng đã sắp xếp, low là chỉ số của phần tử đầu tiên và high là chỉ số của phần tử cuối cùng.
- Bước 2: Kiểm tra phần tử trung bình
Sau khi xác định phần tử trung bình, ta cần kiểm tra xem phần tử này có phải là phần tử cần tìm hay không. Nếu đúng, trả về chỉ số của phần tử đó, rồi đi tới bước 5.
- Bước 3: So sánh phần tử trung bình với giá trị cần tìm
Nếu phần tử trung bình lớn hơn giá trị cần tìm, ta tiếp tục tìm kiếm trong nửa đầu tiên của mảng. Ngược lại, nếu phần tử trung bình nhỏ hơn giá trị cần tìm, ta tiếp tục tìm kiếm trong nửa cuối của mảng.
- Bước 4: Lặp lại quá trình cho đến khi trả về kết quả tìm kiếm
Tiếp tục lặp lại quá trình trên cho đến khi tìm được phần tử cần tìm hoặc khi không tìm thấy phần tử đó trong mảng.
- Bước 5: In ra kết quả tìm kiếm
In ra kết quả vừa tìm được ở các bước trên.
Dưới đây là đoạn code triển khai thuật toán tìm kiếm nội suy:
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high && key >= arr[low] && key <= arr[high]) // vòng lặp diễn ra khi thỏa mãn 2 đkiện trên
{
//bước 1: tìm giá trị trung bình của mảng
int mid = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
//bước 2: kiểm tra phần tử trung bình
if (arr[mid] == key) {
return mid;
}
//bước 3: So sánh phần tử trung bình với giá trị cần tìm
if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
Để hiểu được thuật toán tìm kiếm nội suy (interpolation search) trong Java, freetuts sẽ cung cấp một ví dụ cụ thể dưới đây.
Chương trình triển khai thuật toán tìm kiếm nội suy (interpolation search) trong Java
Bài toán: Cho mảng arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] và giá trị cần tìm là key = 14.
Dưới đây là chương trình Java triển khai thuật toán nội suy để giải quyết bài toán trên.\
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high && key >= arr[low] && key <= arr[high]) {
int mid = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 12, 13, 14, 16, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
int key = 14;
int index = interpolationSearch(arr, key);
System.out.println("Học lập trình miễn phí tại freetuts");
if (index != -1) {
System.out.println( "Đã tìm thấy số " + key + " trong mảng tại vị trí " + index);
} else {
System.out.println("Không tìm thấy phần tử này trong mảng!");
}
}
}
Kết quả:
Học lập trình miễn phí tại freetuts Đã tìm thấy số 14 trong mảng tại vị trí 3
Như vậy là chúng ta đã thực hiện xong chương trình kiểm tra một số có trong mảng. Cũng như kết thúc hướng dẫn thuật toán tìm kiếm nội suy trong Java.
Chúc các bạn thực hiện thành công!!!
