Question

Đã trả lời bởi chuyên gia

Answer 1

Tìm kiếm tuần tự (Linear Search)
Ý tưởng:
Duyệt từng phần tử trong danh sách từ đầu đến cuối để tìm giá trị cần tìm.

Cách làm:

Bắt đầu từ phần tử đầu tiên
So sánh với giá trị cần tìm
Nếu bằng thì dừng
Nếu không thì chuyển sang phần tử tiếp theo
Lặp lại cho đến khi tìm thấy hoặc hết danh sách
Ví dụ:
Danh sách: 3, 7, 2, 9
Tìm số 2
→ so sánh 3 (không) → 7 (không) → 2 (đúng) → dừng

Đặc điểm:

Không cần sắp xếp dữ liệu
Dễ thực hiện
Tốc độ chậm nếu dữ liệu nhiều

Tìm kiếm nhị phân (Binary Search)
Điều kiện:
Danh sách phải được sắp xếp tăng hoặc giảm.

Ý tưởng:
Luôn so sánh với phần tử ở giữa, sau đó loại bỏ một nửa danh sách mỗi lần.

Cách làm:

Xác định phần tử giữa
So sánh với giá trị cần tìmNếu bằng thì dừng
Nếu nhỏ hơn thì tìm bên trái
Nếu lớn hơn thì tìm bên phải
Lặp lại với phần còn lại
Ví dụ:
Danh sách: 1, 3, 5, 7, 9
Tìm số 7
→ giữa là 5 → 7 lớn hơn 5 → tìm bên phải
→ giữa là 7 → tìm thấy

Đặc điểm:

Nhanh hơn nhiều so với tìm kiếm tuần tự
Bắt buộc phải sắp xếp trước

...Xem thêm

Answer 2

Tìm kiếm tuần tự (Linear Search)
Ý tưởng:
Duyệt từng phần tử trong danh sách từ đầu đến cuối để tìm giá trị cần tìm.

Cách làm:

Bắt đầu từ phần tử đầu tiên
So sánh với giá trị cần tìm
Nếu bằng thì dừng
Nếu không thì chuyển sang phần tử tiếp theo
Lặp lại cho đến khi tìm thấy hoặc hết danh sách
Ví dụ:
Danh sách: 3, 7, 2, 9
Tìm số 2
→ so sánh 3 (không) → 7 (không) → 2 (đúng) → dừng

Đặc điểm:

Không cần sắp xếp dữ liệu
Dễ thực hiện
Tốc độ chậm nếu dữ liệu nhiều

Tìm kiếm nhị phân (Binary Search)
Điều kiện:
Danh sách phải được sắp xếp tăng hoặc giảm.

Ý tưởng:
Luôn so sánh với phần tử ở giữa, sau đó loại bỏ một nửa danh sách mỗi lần.

Cách làm:

Xác định phần tử giữa
So sánh với giá trị cần tìmNếu bằng thì dừng
Nếu nhỏ hơn thì tìm bên trái
Nếu lớn hơn thì tìm bên phải
Lặp lại với phần còn lại
Ví dụ:
Danh sách: 1, 3, 5, 7, 9
Tìm số 7
→ giữa là 5 → 7 lớn hơn 5 → tìm bên phải
→ giữa là 7 → tìm thấy

Đặc điểm:

Nhanh hơn nhiều so với tìm kiếm tuần tự
Bắt buộc phải sắp xếp trước

Answer 3

Cách hoạt động:
Bắt đầu từ phần tử đầu tiên của danh sách.
So sánh phần tử hiện tại với giá trị cần tìm.
Nếu bằng nhau, trả về vị trí (index) của phần tử đó.
Nếu không bằng, chuyển sang phần tử tiếp theo.
Lặp lại bước 2-4 cho đến khi tìm thấy phần tử hoặc hết danh sách.
Đặc điểm:
Điều kiện: Danh sách không cần sắp xếp trước.
Độ phức tạp: Thời gian chạy là O𝑛là số lượng phần tử.

Tìm kiếm nhị phân (Binary Search)
Cách hoạt động:
Bắt đầu bằng việc kiểm tra phần tử ở giữa của danh sách đã sắp xếp.
Nếu phần tử ở giữa bằng giá trị cần tìm, trả về vị trí đó.
Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, loại bỏ nửa sau của danh sách và tiếp tục tìm kiếm ở nửa trước.
Nếu giá trị cần tìm lớn hơn phần tử ở giữa, loại bỏ nửa trước của danh sách và tiếp tục tìm kiếm ở nửa sau.
Lặp lại quy trình cho đến khi tìm thấy phần tử hoặc danh sách con không còn phần tử nào.

Đặc điểm:
Điều kiện: Danh sách bắt buộc phải được sắp xếp trước.
Độ phức tạp: Thời gian chạy là O(logn)
, nhanh hơn rất nhiều so với tìm kiếm tuần tự trên dữ liệu lớn.
Tìm kiếm tuần tự duyệt từng phần tử một, còn tìm kiếm nhị phân chia đôi danh sách (đã sắp xếp) liên tục để tìm nhanh hơn.

...Xem thêm

Answer 4

Cách hoạt động:
Bắt đầu từ phần tử đầu tiên của danh sách.
So sánh phần tử hiện tại với giá trị cần tìm.
Nếu bằng nhau, trả về vị trí (index) của phần tử đó.
Nếu không bằng, chuyển sang phần tử tiếp theo.
Lặp lại bước 2-4 cho đến khi tìm thấy phần tử hoặc hết danh sách.
Đặc điểm:
Điều kiện: Danh sách không cần sắp xếp trước.
Độ phức tạp: Thời gian chạy là O𝑛là số lượng phần tử.

Tìm kiếm nhị phân (Binary Search)
Cách hoạt động:
Bắt đầu bằng việc kiểm tra phần tử ở giữa của danh sách đã sắp xếp.
Nếu phần tử ở giữa bằng giá trị cần tìm, trả về vị trí đó.
Nếu giá trị cần tìm nhỏ hơn phần tử ở giữa, loại bỏ nửa sau của danh sách và tiếp tục tìm kiếm ở nửa trước.
Nếu giá trị cần tìm lớn hơn phần tử ở giữa, loại bỏ nửa trước của danh sách và tiếp tục tìm kiếm ở nửa sau.
Lặp lại quy trình cho đến khi tìm thấy phần tử hoặc danh sách con không còn phần tử nào.

Đặc điểm:
Điều kiện: Danh sách bắt buộc phải được sắp xếp trước.
Độ phức tạp: Thời gian chạy là O(logn)
, nhanh hơn rất nhiều so với tìm kiếm tuần tự trên dữ liệu lớn.
Tìm kiếm tuần tự duyệt từng phần tử một, còn tìm kiếm nhị phân chia đôi danh sách (đã sắp xếp) liên tục để tìm nhanh hơn.

2 câu trả lời 36

Câu hỏi hot cùng chủ đề

Bài viết mới nhất Lớp 7