AP Computer Science AAP Computer Science Principles
linear searchVietnamese: tìm kiếm tuần tự
Còn gọi:Also called: sequential search
Tìm kiếm tuần tự (linear search) là thuật toán kiểm tra lần lượt từng phần tử từ đầu tới cuối cho tới khi gặp giá trị cần tìm.
Trực giác: Như tìm chìa khoá trong chùm: thử từng chiếc một cho đến khi mở được cửa.
Thuật toán duyệt từng vị trí, so sánh với giá trị đích, trả về vị trí đầu tiên khớp hoặc báo không tìm thấy (Java thường trả về -1). Không cần dữ liệu đã sắp xếp nên dùng được mọi lúc. Khác tìm kiếm nhị phân, nó chậm hơn trên list dài vì trường hợp xấu nhất phải xem hết mọi phần tử.
Viết if (arr[i] == target) return i; else return -1; trong vòng là sai, vì vòng dừng ngay ở phần tử đầu.
Với String phải so sánh bằng equals, không dùng ==.
Trả về chỉ số lần gặp đầu tiên; giá trị lặp lại phía sau không được trả về.
AP Computer Science A: Đặt return -1 sau vòng lặp, không đặt trong nhánh else bên trong vòng, nếu không chỉ phần tử đầu được kiểm tra.
AP Computer Science A: Dùng được cho mảng chưa sắp xếp; trường hợp xấu nhất kiểm tra hết n phần tử.
AP Computer Science Principles: Tìm kiếm tuần tự chạy trên mọi list, còn tìm kiếm nhị phân đòi list đã sắp xếp.
AP Computer Science Principles: Số lần so sánh xấu nhất tăng tuyến tính theo độ dài list.
public static int find(int[] arr, int target) { for (int i = 0; i < arr.length; i++) { if (arr[i] == target) return i; } return -1; } // find(new int[]{4, 8, 2, 8}, 8) trả về 1; tìm 5 trả về -1 Vòng dừng ngay ở số 8 đầu tiên (chỉ số 1). Chỉ khi duyệt hết mà không thấy mới trả về -1.
Quiz câu thật từ ngân hàng đềReal exam questions from our question bank
Vài câu thật gắn đúng khái niệm này, chấm ngay kèm giải thích từng đáp án — hệ thống ghi nhớ bạn nắm tới đâu.A few real questions on exactly this concept, graded instantly with an explanation for every choice — the system remembers how well you know it.
Biên soạn bởi DucklingStudy, bản quyền thuộc DucklingStudy.Written by DucklingStudy. © DucklingStudy. Xuất bảnPublished .