AP Computer Science AAP Computer Science Principles

tìm kiếm tuần tựlinear search

linear searchVietnamese: tìm kiếm tuần tự

Còn gọi:Also called: sequential search

Định nghĩaIn short

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.

Định nghĩa đầy đủ1 phút đọc

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ử.

Hay hiểu sai3 ý, 1 phút đọc

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ề.

Mẹo phòng thi4 mẹo

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.

Tần suất trong đề AP Computer Science AHow often it shows up on AP Computer Science AHiếm gặpRare
Tần suất trong đề AP Computer Science PrinciplesHow often it shows up on AP Computer Science PrinciplesÍt gặpUncommon
Ví dụ có lời giải1 phút đọc
Viết method trả về chỉ số đầu tiên chứa target, hoặc -1.

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.

Bạn nắm chắc chưa?Check your understanding

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.

Tạo tài khoảnCreate an account

Học tiếp từ đâyKeep learning

Bài học chứa thuật ngữ nàyLesson that uses this termThuật toán tìm kiếmCấu trúc dữ liệu tập hợp, khoácourse AP Computer Science A
Bài học chứa thuật ngữ nàyLesson that uses this termDanh sáchThuật toán & lập trình, khoácourse AP Computer Science Principles
Mục tiêu và lộ trình unit ai cũng xem được — làm bài tập và lưu tiến độ thì cần đăng nhập.Anyone can view a unit's goals and roadmap — sign in to do the exercises and save your progress.

Cùng chủ đềSame topic

Biên soạn bởi DucklingStudy, bản quyền thuộc DucklingStudy.Written by DucklingStudy. © DucklingStudy. Xuất bảnPublished .