Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Thuật toán tìm kiếm nhị phân được thực hiện trên một danh sách đã được (1) sắp xếp. Bắt đầu từ vị trí ở (2) giữa của danh sách. Tại mỗi bước, ta so sánh giá trị cần tìm với giá trị ở vị trí đó. Nếu giá trị cần tìm lớn hơn, ta tìm ở (3) nửa phải của danh sách. Nếu nhỏ hơn, ta tìm ở (4) nửa trái của danh sách.
Thuật toán tìm kiếm nhị phân được mô tả bằng ngôn ngữ tự nhiên:
- Bước 1: Xác định danh sách (mảng) đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
- Bước 2: Đặt hai biến trái và phải lần lượt là chỉ số phần tử đầu và phần tử cuối của danh sách.
- Bước 3: Tính chỉ số giữa = (trái + phải) / 2 (lấy phần nguyên).
- Bước 4: So sánh giá trị cần tìm với phần tử ở vị trí giữa:
+ Nếu bằng, thì kết thúc và trả về vị trí giữa.
+ Nếu nhỏ hơn, thì cập nhật phải = giữa - 1 để tiếp tục tìm trong nửa bên trái.
+ Nếu lớn hơn, thì cập nhật trái = giữa + 1 để tiếp tục tìm trong nửa bên phải.
- Bước 5: Lặp lại bước 3 và bước 4 cho đến khi tìm thấy hoặc khi trái > phải (nghĩa là không có phần tử cần tìm).
Sự khác biệt cơ bản nhất là thuật toán tìm kiếm nhị phân yêu cầu dữ liệu phải được sắp xếp, trong khi thuật toán tìm kiếm tuần tự không có yêu cầu này. Ngoài ra, cách thức tìm kiếm của thuật toán nhị phân là chia để trị, còn thuật toán tuần tự là duyệt lần lượt từng phần tử
Tìm kiếm tuần tự duyệt từng phần tử một, không cần sắp xếp. Tìm kiếm nhị phân chia đôi danh sách mỗi bước, cần sắp xếp trước.
Vì tìm kiếm nhị phân cần danh sách đã sắp xếp để biết chắc phần tử cần tìm nằm ở bên trái hay bên phải. Nếu không sắp xếp, ta không thể loại bỏ nửa danh sách một cách chính xác
Bạn lớp 4 à ?