Đề 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
Bài tập về tìm nhị phân
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ị left và right ngay đầu vòng while xem.
-
Nếu
right - left == 1thìmid = (left + right) / 2 == left. Giả sử nếua[left] = 1, x = 2, a[right] = 3thì code của bạn lặp vô hạn ngay. -
Một trường hợp nữa,
left == right, giả sửa[left] = 1,x = 0thì ở lượt tiếp theoright = mid - 1 == left - 1thì 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 
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ả.
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 > và < đề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ử 
trong hàm vitri() sao ko reset biết dem = 0
3 Likes
tìm nhị phân dùng đệ quy dễ hiểu hơn đó.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?