CĂN BẢN
CHUỖI
VÒNG LẶP
NUMBER
INPUT / OUTPUT
COLLECTIONS
Ví dụ danh sách liên kết đơn Java Đếm số node trong Singly Linked List trong Java Đảo ngược thứ tự của Singly Linked List trong Java Xóa node đầu tiên của Singly Linked List trong Java Xóa node ở giữa của Singly Linked List trong Java Xóa node cuối cùng của Singly Linked List trong Java Thêm node vào vị trí đầu tiên của Singly Linked List trong Java Thêm node vào vị trí cuối cùng của Singly Linked List trong Java Thêm node vào vị trí giữa của Singly Linked List trong Java Kiểm tra danh sách liên kết đơn palindrome trong Java Tìm giá trị lớn nhất của Singly Linked List trong Java Tìm giá trị nhỏ nhất của Singly Linked List trong Java Xóa phần tử trùng lặp khỏi Singly Linked List trong Java Tìm kiếm phần tử của Singly Linked List trong Java Tạo một Circular Linked List trong Java Tạo một Circular Linked List Java và đảo ngược nó Xóa node đầu tiên của Circular Linked List trong Java Xóa node cuối cùng của Circular Linked List trong Java Xóa node ở giữa của Circular Linked List trong Java Thêm node vào vị trí đầu tiên của Circular Linked List trong Java Thêm node vào vị trí cuối cùng của Circular Linked List trong Java Thêm node vào vị trí giữa của Circular Linked List trong Java Tìm giá trị lớn nhất trong Circular Linked List Java Tìm giá trị nhỏ nhất trong Circular Linked List Tìm kiếm phần tử của Circular Linked List trong Java Xóa phần tử trùng lặp khỏi Circular Linked List trong Java Sắp xếp các phần tử của Circular Linked List trong Java Chuyển đổi Binary Tree thành Double Linked List trong Java Tạo double linked list từ cây bậc ba (ternary tree) trong Java Cách chuyển đổi từ cây nhị phân thành cây nhị phân tìm kiếm trong Java Xác định các lá có cùng cấp trong Tree của Java Kiểm tra hai cây giống nhau trong Java Tìm chiều rộng tối đa của cây nhị phân trong Java Tìm phần tử lớn nhất của cây nhị phân trong Java Tìm khoảng cách lớn nhất giữa các node của cây nhị phân trong Java Tìm phần tử nhỏ nhất của cây nhị phân trong Java Tính tổng giá trị của các node của cây nhị phân trong Java Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java Triển khai cây nhị phân từ danh sách liên kết trong Java Tìm kiếm node của cây nhị phân tìm kiếm trong Java Cách tạo ra Mirror Tree từ Binary Tree bằng ngôn ngữ Java Xác định các lá của binary tree sử dụng preoder trong Java Xác định đường biên(boundary traversal) của cây nhị phân trong Java Xóa node của cây nhị phân tìm kiếm trong Java Duyệt cây nhị phân bằng phương pháp inOder trong Java
CALCULATE
SẮP XẾP - TÌM KIẾM
KHÁC
NÂNG CAO
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thứ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!!!

Cùng chuyên mục:

Hướng dẫn Upload file với Spring Boot và jQuery Ajax trong Java

Hướng dẫn Upload file với Spring Boot và jQuery Ajax trong Java

Hướng dẫn download file với Spring Boot trong Java

Hướng dẫn download file với Spring Boot trong Java

Hướng dẫn Upload file với Spring Boot trong Java

Hướng dẫn Upload file với Spring Boot trong Java

Hướng dẫn CRUD với Spring Boot, REST và AngularJS trong Java

Hướng dẫn CRUD với Spring Boot, REST và AngularJS trong Java

Cách sử dụng Spring  Scheduled trong Spring Boot

Cách sử dụng Spring Scheduled trong Spring Boot

Cách dùng Groovy trong Spring Boot Java

Cách dùng Groovy trong Spring Boot Java

Cách dùng Spring Boot và Mustache trong Java

Cách dùng Spring Boot và Mustache trong Java

Cách dùng Spring Boot và MongoDB trong Java

Cách dùng Spring Boot và MongoDB trong Java

Cách tạo Restful Client bằng RestTemplate trong Spring Boot

Cách tạo Restful Client bằng RestTemplate trong Spring Boot

Hướng dẫn sử dụng Interceptor trong Spring Boot

Hướng dẫn sử dụng Interceptor trong Spring Boot

Sử dụng Twitter Bootstrap trong Spring Boot

Sử dụng Twitter Bootstrap trong Spring Boot

Tạo trang web đa ngôn ngữ với Spring Boot trong Java

Tạo trang web đa ngôn ngữ với Spring Boot trong Java

Tạo ứng dụng Chat với Spring Boot và Websocket

Tạo ứng dụng Chat với Spring Boot và Websocket

Sử dụng JUnit để tạo unit test trong Spring Boot

Sử dụng JUnit để tạo unit test trong Spring Boot

Cách triển khai Spring Boot trên Tomcat Server

Cách triển khai Spring Boot trên Tomcat Server

Cách test RESTful API trong Spring Boot

Cách test RESTful API trong Spring Boot

Cách dùng Spring Security trong Spring Boot để xác thực và phân quyền

Cách dùng Spring Security trong Spring Boot để xác thực và phân quyền

Duyệt cây nhị phân bằng phương pháp inOder trong Java

Duyệt cây nhị phân bằng phương pháp inOder trong Java

Xóa node của cây nhị phân tìm kiếm trong Java

Xóa node của cây nhị phân tìm kiếm trong Java

Bảo mật Spring Boot RESTful Service sử dụng Basic Authentication trong Java

Bảo mật Spring Boot RESTful Service sử dụng Basic Authentication trong Java

Top