Bài toán tìm kiếm
Tóm tắt
Bài học so sánh tìm kiếm tuần tự với tìm kiếm nhị phân trên dãy đã sắp xếp.
Hiểu bài
Bài toán tìm kiếm xác định một giá trị hoặc đối tượng trong miền dữ liệu. Tìm kiếm tuần tự duyệt lần lượt từ đầu đến cuối cho đến khi gặp phần tử bằng khoá cần tìm; hàm mẫu trả về chỉ số nếu thấy, ngược lại trả về -1. Tìm kiếm nhị phân chỉ áp dụng khi dãy đã được sắp xếp. Thuật toán duy trì left, right, tính mid = (left + right)//2; nếu A[mid] nhỏ hơn khoá thì chuyển left = mid + 1, ngược lại thu hẹp phía phải. Sau mỗi vòng, phạm vi tìm kiếm giảm dần.
Các giá trị được xét theo từng bước tìm kiếm SGK trang 93