Linear Search - Tìm Kiếm Tuyến Tính
Tìm hiểu về Linear Search - tìm kiếm tuyến tính qua code mẫu.
15/08/2015
17/08/2020
2 phút đọc
17/08/2020
2 phút đọc

Linear Search
Linear search có các tên gọi khác như Sequential search – Tìm kiếm tuần tự – Tìm kiếm tuyến tính là 1 trong các giải thuật hỗ trợ tìm kiếm 1 phần tử trong mảng.
Ý tưởng
Tìm kiếm từ đầu cho đến cuối mảng (hoặc ngược lại).
- Nếu tìm thấy trả vị trí của kết quả tìm kiếm.
- Nếu không tìm thấy thì trả về 1.

Code mẫu Linear Search
#include <iostream> using namespace std; int LinearSearch(int arr[], int numberOfElements, int key) { for (int i = 0; i < numberOfElements; i++) if (arr[i] == key) return i; return -1; } int main() { int arr[] = { 10, 8, 1, 21, 7, 32, 5, 11, 0 }; int size = sizeof(arr) / sizeof(arr[0]); int index = LinearSearch(arr, size, 5); if (index == -1) cout << "Khong tim thay!" << endl; else cout << "Vi tri tim thay la: " << index << endl; return 0; }
Output: Vi tri tim thay la: 6
.
Các bước thực hiện
- Bước 1: Duyệt mảng từ vị trí đầu tiên
i = 0
. - Bước 2: Thực hiện so sánh
arr[i]
vàkey
. Nếuarr[i] == key
trả về vị tríi
.- Trong trường hợp này hàm sẽ trả về giá trị
i = 6
do 7 nằm ở vị trí thứ 6.
- Trong trường hợp này hàm sẽ trả về giá trị
- Bước 3: Nếu duyệt hết mảng vẫn không tìm thấy thì trả về
-1
.
Đánh giá
- Trong trường hợp tốt nhất, phần tử cần tìm nằm ở vị trí đầu tiên, thuật toán sử dụng 1 lần so sánh.
- Trong trường hợp xấu nhất, phần tử cần tìm nằm ở vị trí cuối hoặc không nằm trong mảng, thuật toán sử dụng
n - 1
lần so sánh. - Linear Search là một giải thuật đơn giản khi hiện thực và khá hiệu quả với danh sách đủ nhỏ hoặc một danh sách chưa được sắp xếp.
Giải Thuật Lập Trình
STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.
Đăng ký
Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.