Linear search hay còn lại là tìm kiếm tuần tự, là một phương pháp tìm kiếm một phần tử cho trước trong một danh sách bằng cách duyệt lần lượt từng phần tử cho đến khi tìm thấy giá trị mong muốn hoặc không tìm thấy nếu đã duyệt hết mảng.
Các bước thực hiện
B1: Khởi tạo biến i = 0;
B2: Trong khi i < n
+ Nếu arr[i] == X return i
+ i = i + 1
B3: return -1 nếu không tìm thấy
Implementation
public static <T> int search(T[] arr, int n, T x) {
for (int i = 0; i < n; i++)
if (x.equals(arr[i]))
return i;
return -1;
}
Độ phức tạp của Linear search là θ(n)