Bài toán tìm kiếm

Hiểu bài

Bài toán tìm kiếm xác định một hoặc nhiều phần tử thoả tiêu chí trong miền dữ liệu. Tìm kiếm tuần tự duyệt lần lượt các phần tử từ đầu đến cuối, dừng khi gặp giá trị cần tìm hoặc đã duyệt hết. Hàm minh hoạ trả về chỉ số khi A[i] == K, ngược lại trả về -1.

Tìm kiếm nhị phân chỉ áp dụng cho dãy đã sắp xếp. Thuật toán duy trì hai biên left, right, lấy mid = (left + right)//2; nếu A[mid] nhỏ hơn giá trị cần tìm thì chuyển biên trái sang mid + 1, ngược lại chuyển biên phải sang mid - 1. Sau mỗi bước, phạm vi tìm kiếm được thu hẹp:

while left <= right:
    mid = (left + right)//2

Tìm kiếm nhị phân thường cần ít bước hơn trên dãy đã sắp xếp.