Hỏi thuật toán tìm kiếm nội suy

Tran_Hai_Anh · June 20, 2022, 3:00pm

int search(int *a, int n, int x){
    int mid, low=0, high=n-1;
    while ((a[high]!=a[low])&&(x>=a[low])&&(x<=a[high])){
        mid=l+((x-a[low])*(high-low)/(a[high]-a[low]));
        if(a[mid]<x){
            l=mid+1;
        }
        else if(x<a[mid]){
            h=mid-1;
        }
        else return mid;
    }
    if(x==a[low]){
        return low;
    }
    else return -1;
}

Mình không rõ sao cần điều kiện a[high]!=a[low]. Nó đâu cần thiết vì nếu gặp trường hợp hội tụ về cuối high = low nên a[high] = a[low] thì chắc chắn vòng lặp dừng vì x có thể không đáp ứng được điều kiện (x>=a[low]) hay (x<=a[high]), còn nếu đáp ứng để vòng lặp chạy tiếp thì dừng ngay tại " else return mid; " rồi, khi đó low = mid = high.

tntxtnt · June 20, 2022, 3:51pm

tại vì nó cần chia cho (a[high]-a[low]) kìa :V Nếu a[high] == a[low] thì chia 0 bị lỗi ngay :V

Tran_Hai_Anh · June 21, 2022, 7:35am

Code vẫn chạy được nhỉ Test thử 1000 số vẫn chưa thấy gì, chắc thử xem vài lần nữa. Khó kiếm được bộ số quá, toàn ko gặp được bộ số hội tụ để x=a[high]=a[low].

rogp10 · June 21, 2022, 7:36am

Runtime error mà

Tran_Hai_Anh · June 21, 2022, 7:42am

Uk nhỉ, mảng sắp xếp có số trùng lặp.
Mình thử với mảng số sắp xếp không trùng lặp thì thử nãy giờ ko gặp trường hợp nào đạt được x=a[high]=a[low].