TIN 7 - BÀI 15 - NHỊ PHÂN

Thuật toán tìm kiếm nhị phân yêu cầu dữ liệu phải:

• Có kích thước lớn

• Được sắp xếp theo thứ tự

• Không có phần tử giống nhau

• Ghi bằng ngôn ngữ tự nhiên

Bước đầu tiên trong thuật toán tìm kiếm nhị phân là:

• Tìm phần tử ở cuối

• Tìm phần tử ở đầu

• Tìm phần tử ở giữa

• So sánh với tất cả phần tử

Khi tìm kiếm nhị phân, nếu phần tử cần tìm nhỏ hơn phần tử giữa, ta:

• Chuyển sang bên phải

• Chuyển sang bên trái

• Kết thúc tìm

• Đổi vị trí phần tử

Tìm kiếm nhị phân sử dụng cấu trúc:

• Tuần tự

• Rẽ nhánh

• Lặp

• Song song

Thuật toán tìm kiếm nhị phân sẽ kết thúc khi:

• Đếm được n phần tử

• Tìm được hoặc không còn phần tử nào để tìm

• Duyệt hết danh sách

• Đếm được phần tử lặp

Trong tìm kiếm nhị phân, nếu phần tử giữa đúng là phần tử cần tìm thì:

• Tiếp tục tìm

• Tìm sang trái

• Tìm sang phải

• Kết thúc tìm kiếm

Tìm kiếm nhị phân là hiệu quả hơn tìm kiếm tuần tự vì:

• Dễ lập trình

• Ít số lần kiểm tra hơn

• Dùng ít bộ nhớ

• Không cần sắp xếp

Danh sách cần tìm trong tìm kiếm nhị phân phải được:

• Đổi vị trí mỗi lần tìm

• Gán lại chỉ số

• Sắp xếp tăng hoặc giảm

• Thêm phần tử mới

Số lượng phần tử giảm đi sau mỗi bước tìm kiếm nhị phân là:

• 1 phần tử

• 3 phần tử

• Một nửa số phần tử còn lại

• Tất cả phần tử

Khi còn 1 phần tử trong vùng tìm kiếm mà không trùng với giá trị cần tìm:

• Tìm lại từ đầu

• Xoá phần tử đó

• Kết thúc và thông báo không tìm thấy

• Dừng chương trình