Em mãi không giác ngộ được tìm kiếm nhị phân, tìm kiếm nhị phân kết quả, chỉ làm được mấy bài rất cơ bản như kiểm tra xem phần tử có trong mảng hay không,… Ai giúp em với, em cảm ơn ạ
Không làm được bài tập về tìm kiếm nhị phân
giúp kiểu gì? gõ 1 mớ thứ cho bạn đọc để bạn giác ngộ?
1 Like
Mẹo để “giác ngộ” binary search: đừng nghĩ nó là “tìm phần tử”, mà hãy nghĩ nó là “thu hẹp khoảng chứa đáp án một nửa sau mỗi bước”. Bạn giữ hai biến lo, hi và luôn đảm bảo đáp án nằm trong [lo, hi]. Mỗi vòng lấy mid = lo + (hi - lo) / 2, rồi dựa vào điều kiện đúng/sai tại mid mà bỏ nửa trái hoặc nửa phải (lo = mid + 1 hoặc hi = mid - 1).
Với các bài “tìm kiếm nhị phân kết quả” (tìm giá trị nhỏ nhất thoả điều kiện X), bạn viết hàm check(x) trả về true/false, mảng/khoảng giá trị sẽ dạng FFFFTTTT, và nhiệm vụ là tìm vị trí T đầu tiên. Khi check(mid) đúng thì lưu ans = mid rồi tìm tiếp bên trái (hi = mid - 1), sai thì lo = mid + 1. Bạn thử bài đơn giản như tính căn bậc hai nguyên của n bằng cách này trước, rồi đăng đề bài cụ thể đang bí lên để mọi người chỉ rõ hơn nhé.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?