Cấu trúc dữ liệu và giải thuật - Tìm kiếm

Tìm kiếm tuyến tính

Tìm kiếm tuyến tính là một giải thuật tìm kiếm cơ bản. Với kiểu tìm kiếm này, ta tiến hành tìm kiếm từng phần tử một trong tập dữ liệu.

Tìm kiếm nhị phân

Tìm kiếm nhị phân là một giải thuật tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο(log n). Giải thuật tìm kiếm nhị phân dựa trên nguyên tắc chia để trị (Divide and Conquer).

Tìm kiếm nội suy

Tìm kiếm nội suy là biến thể cải tiến của tìm kiếm nhị phân. Để giải thuật này hoạt động chính xác, tập dữ liệu phải được sắp xếp.

Mã giả của tìm kiếm tuyến tính

1. Thiết lập i thành 1
2. Nếu i > n thì chuyển tới bước 7
3. Nếu A[i] = x thì chuyển tới bước 6
4. Thiết lập i thành i + 1
5. Tới bước 2
6. In phần tử x được tìm thấy tại chỉ mục i và tới bước 8
7. In phần tử không được tìm thấy
8. Thoát

Mã giả của tìm kiếm nhị phân

1. Thiết lập lowerBound thành 0
2. Thiết lập upperBound thành số phần tử trong mảng
3. Lặp lại cho tới khi lowerBound không nhỏ hơn upperBound
   • Tính midIndex = lowerBound + (upperBound - lowerBound) / 2
   • Nếu A[midIndex] = x thì trả về midIndex
   • Nếu A[midIndex] x thì thiết lập lowerBound thành midIndex + 1
   • Nếu A[midIndex] > x thì thiết lập upperBound thành midIndex
4. Trả về không tìm thấy

Mã giả của tìm kiếm nội suy

1. Thiết lập lowerBound thành 0
2. Thiết lập midIndex thành -1
3. Thiết lập upperBound thành số phần tử trong mảng trừ 1
4. Lặp lại cho tới khi lowerBound khác upperBound và A[lowerBound] khác A[upperBound]
   • Tính midIndex = lowerBound + ((upperBound - lowerBound) / (A[upperBound] - A[lowerBound])) * (x - A[lowerBound])
   • Nếu A[midIndex] = x thì trả về midIndex
   • Nếu A[midIndex] x thì thiết lập upperBound thành midIndex + 1
   • Nếu A[midIndex] > x thì thiết lập upperBound thành midIndex - 1
5. Trả về không tìm thấy

Để xem mã nguồn chi tiết về các thuật toán tìm kiếm, bạn có thể tham khảo repository GitHub dưới đây:

https://github.com/pqhuy87it/MonthlyReport/tree/master/SearchAlgorithms