Linear Search (Tìm kiếm tuyến tính) là một thuật toán tìm kiếm cơ bản và rất đơn giản. Trong Linear Search, chúng ta tìm kiếm một phần tử hoặc giá trị trong một mảng nhất định bằng cách duyệt mảng từ đầu tới khi tìm thấy phần tử hoặc giá trị mong muốn.
1. Đặc điểm của Linear Search
Thuật toán sẽ so sánh phần tử được tìm kiếm với tất cả các phần tử có trong danh sách và khi tìm khớp thành công, nó trả về chỉ mục của phần tử trong danh sách, nếu không nó sẽ trả về -1.
Linear Search được áp dụng cho các danh sách chưa được sắp xếp (unsorted), hoặc không có thứ tự (unordered), và tập dữ liệu cần thao tác nhỏ.
Nó có độ phức tạp thời gian (Time Complexity) là O(n), có nghĩa là thời gian phụ thuộc tuyến tính vào số lượng phần tử.
Lấy ví dụ một mảng với các giá trị {10, 14, 19, 26, 27, 31, 33, 35, 42, 44}. Hình ảnh dưới đây sẽ mô tả tìm kiếm vị trí của phần tử có giá trị là 33 ở trong mảng bằng Linear Search:
2. Cài đặt Linear Search
Mã code dưới đây mô tả cách cài đặt Linear Search trong Java:
LinearSearch
package com.icancodeit.algorithm.searching.linear;
public class LinearSearch {
private static int search(int[] arr, int x) {
for (int i = 0, length = arr.length; i < length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = {10, 14, 19, 26, 27, 31, 33, 35, 42, 44};
int x = 33;
int result = search(arr, x);
if (result == -1)
System.out.print("Element is not present in array");
else
System.out.print("Element is present at index = " + result);
}
}
Kết quả
Element is present at index = 6
3. Phân tích độ phức tạp của Linear Search
- Time Complexity: O(n)
Có thể nhiều người sẽ thích Linear Search, bởi vì nó rất đơn giản và dễ cài đặt. Tuy nhiên nó rất ít được sử dụng trong thực tế, vì nó không hiệu quả với tập dữ liệu có kích thước lớn. Một trong các thuật toán tìm kiếm được dùng phổ biến và hiệu quả hơn Linear Search là Binary Search (Tìm kiếm nhị phân).
Đọc thêm:
https://www.studytonight.com/data-structures/linear-search-algorithm
TÙNG'S BLOG 