Bài tập về tìm nhị phân

image
Đề bài của em như thế này: Hãy cài đặt thuật toán tìm kiếm nhị phân để tìm vị trí của phần tử x trong mảng có N phần tử và đếm số lần duyệt qua các phần tử.
Hàm em tạo ra vừa để tính số lần chạy và tìm vị trí cùng một lúc. Không biết có cách nào làm nhanh hơn không ạ vì khi nộp bài em bị time limited

Code tìm kiếm nhị phân bị time limit exceeded thì 100% do bị lặp vô hạn. Không tin thì bạn thử in ra giá trị leftright ngay đầu vòng while xem.

  1. Nếu right - left == 1 thì mid = (left + right) / 2 == left. Giả sử nếu a[left] = 1, x = 2, a[right] = 3 thì code của bạn lặp vô hạn ngay.

  2. Một trường hợp nữa, left == right, giả sử a[left] = 1, x = 0 thì ở lượt tiếp theo right = mid - 1 == left - 1 thì có khả năng lại rơi tiếp vào trường hợp 1.


P/s: Rất hạn chế tái chế biến n kiểu như code của bạn. Đối với các bài competitive programming, tạo thêm 1 biến 4 byte có mất gì đâu mà bạn phải xài lại như vậy :neutral_face: vừa tạo thói quen xấu vừa khó debug.

Ko ạ, bài của em khi chạy chương trình vẫn chạy được bình thường, vẫn in ra kết quả đúng. Nhưng khi nộp bài thì bị limited (do tốc độ chạy của gv nhanh hơn) nên em muốn tìm cách để tăng tốc vòng lặp. Theo như đề bài thì em mới tạo thêm một biến để đếm số vòng lặp chạy. Nên em mới muốn biết có cách nào để chạy nhanh hơn hay do của em bị chậm hơn so với bình thường


Như trường hợp 1 thì em vẫn cho chạy được bình thường.
(Cảm ơn vì ps của anh, em sẽ khắc phục cái này)

Bạn đăng đầy đủ đề bài (kèm giới hạn tất cả các tham số), limit time và limit memory lên đây. Limit time luôn có 1 con số chuẩn, không ai tính theo mốc thời gian chạy solution của người khác cả.


chỉ có nhiêu đây thôi ạ

Bạn có link nộp bài không?

Nếu thời gian chạy là 1s thì mình khẳng định code bạn bị lặp vô hạn dẫn đến time limit exceeded chứ không phải code bạn chậm hơn code của giáo viên nhé.

Có dòng

int mid = (left + right) / 2;

có thể dẫn đến tràn số (mặc dù mình không nghĩ vậy). Bạn thử sửa thành

int mid = left + (right - left) / 2;

xem sao. Nếu sửa rồi mà vẫn bị lặp vô hạn thì do dòng gán lại left/right của bạn có vấn đề.

1 Like

Uầy, Giáo viên của bạn chạy còn nhanh hơn code của bạn à <(")
Nói chứ chụp cả đề ra bạn

Trường hợp >< đều tăng left hay giảm right nên lặp vô tận thì chỉ có thể nghĩ đến overflow.

1 Like

ở trên đấy bạn
toàn bộ đề của bài này

1 Like


còn đây là phần ví dụ.
Cái này là link trường đăng nhập bằng tài khoản cá nhân nhưng vẫn có thể nộp bằng file .cpp, bạn có thể gửi file .cpp giúp mình được không

Chắc là do ko có cin.tie(NULL) gì đấy. Ngay sau int main để dòng

cin.tie(NULL)->sync_with_stdio(false);

với lại đề cho n tới 32000 sao mảng a chỉ có 100 phần tử :hocho: :hocho:

trong hàm vitri() sao ko reset biết dem = 0 :hocho: :hocho:

3 Likes

tìm nhị phân dùng đệ quy dễ hiểu hơn đó.

Điểm yếu dạng toán này là mảng phải được sắp xếp. Bạn có thể xem source code này tham khảo xem

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?