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

#1

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

#2

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.

  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.

#4

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

image
image518×792 23.6 KB

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)

#5

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ả.

#6

image
image1146×791 70.7 KB

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

#7

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é.

#8

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
#9

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

#10

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
#11

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

1 Like
#12

image
image1118×827 58.3 KB

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

#13

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:

2 Likes
#14

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?