Bài tập liên quan đến tìm kiếm nhị phân

Vinh_Nguyen · November 15, 2020, 3:54am

Chào mọi người. Em đang tự học c qua các tài liệu thu thập được. Trong quá trình làm bài tập em có bài này e vẫn chưa tìm ra hướng đi mong mọi người giúp đỡ.

BT: Áp dụng thuật toán tìm kiếm nhị phân trên mảng SV đã sắp xếp tăng dần theo điểm trung bình. Giả sử có nhiều SV cùng điểm trung bình cho phép người dùng trả lời đã đúng sinh viên cần tìm chưa. nếu đúng thì in kết quả ra, nếu chưa thì tiếp tục tìm kiếm.

int tknp(SV a[], int n, int x){
    int la;
    int l=0;
    int r=n-1;
    while(l<=r){
        int m=(l+r)/2;
        if(x==dtb(a[m])){ printf("%s %d %.2f %.2f %.2f %.2f\n", a[m].ten, a[m].msv, a[m].d1, a[m].d2, a[m].d3, dtb(a[m]));
        printf("Day co phai nguoi ban can tim khong?\n");
        scanf("%d", &la);
        if(la==1) return m;
        else 
        }
        else if(x>dtb(a[m])) l=m+1;
             else r=m-1;
    }
    return -1;
}

mong mn giúp đỡ!

Red_Sand · November 15, 2020, 7:35am

Đầu tiên bạn thực hành tìm kiếm nhị phân với mảng chứa các con số trước. Sau khi thành thạo thì chuyển qua mảng sinh viên. Điểm trung bình cũng là các con số, việc so sánh về cơ bản không có gì khác biệt.
Gợi ý: sau khi tìm được điểm số bằng với yêu cầu thì lọc lấy những sinh viên có điểm số tương tự, họ nằm kề nhau trên mảng, nên việc này dễ.