Thắc mắc về giải thuật LinearSearch trong C

Theo em nghĩ nếu như không có dòng a[n] = x; thì khi nhập X không nằm trong mảng thì vòng lặp while sẽ lặp vô hạn nhưng sao em chạy thì vẫn ra kết quả đúng. Mong các cao nhân giúp đỡ đa tạ :smiley:

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void NhapMang(int a[], int n);
void XuatMang(int a[], int n);
int LinearSearch(int a[], int n, int x);
//int LinearSearch1(int a[], int n, int x);
//int LinearSearch2(int a[], int n, int x);

int main()
{
    int n, x;
    printf("Nhap so phan tu cua mang: ");
    scanf("%d", &n);
    int a[n];
    NhapMang(a,n);
    XuatMang(a,n);
    printf("\nNhap vao so X can tim kiem trong mang: ");
    scanf("%d", &x);
    int result1 = LinearSearch(a,n,x);
    if(result1 == -1)
        printf("khong thay X");
    else
        printf("Thay X o vi tri a[%d] khi duyet tu dau den cuoi mang", result1);
    //LinearSearch1(a,n,x);
    //LinearSearch2(a,n,x);
    getch();
    return 0;
}

void NhapMang(int a[], int n)
{
    srand((int)time(NULL));
    for(int i=0; i<n; i++)
        a[i] = rand()%50;
}

void XuatMang(int a[], int n)
{
    for(int i=0; i<n; i++)
    {
        if(i%10==0 && i!=0)
            printf("\n");
        printf("%d\t", a[i]);
    }
}

int LinearSearch(int a[], int n, int x)
{
    int i=0;
    //a[n] = x; phương pháp lính canh
    while (a[i] != x)
        i++;
    if(i<n) return i;
    return -1;
}

Đó là vì trong mảng có giá trị x, nếu không có thì vô hạn

bạn chạy thử đi nếu X không có trong mảng thì nó vẫn in ra "khong thay X " chứ đâu có lặp vô hạn đâu bạn

vòng lặp này ko bao giờ thoát được nếu x ko có trong mảng

Trong C, bạn có thể truy cập phần từ ngoài vùng cấp phát của mảng, ví dụ như a[n], a[n+1], những vị trí này chứa những giá trị “rác”. Vòng lặp không vô hạn vì có thể “đằng sau” mảng (tức là gia trị từ a[n] trở đi) có một giá trị rác nào đó trùng với số cần tìm nhưng lại không nằm trong kích thước mảng thì hàm LinearSearch trả về -1. Nếu không có giá trị nào trùng thì vòng lặp vẫn có thể lặp vô hạn. Bạn thử in ra giá trị của biến i khi chạy xong vòng lặp thì sẽ rõ.

1 Like

bạn chạy thử đi sẽ biết kết quả

có khi nào xảy ra trường hợp này không nhỉ :fearful: .

Mình chạy thử chục lần thì không thấy bị lặp vô hạn, chỉ có 2 khả năng:

  • Một là tìm thấy giá trị rác.
  • Hai là i tăng đến một gia trị nào đó (mình chạy thì là i = 3188), thì “đụng” đến vùng nhớ đặc biệt nào đó gây xung đột (access violation reading…) kết quả dẫn đến chương trình dừng lại không chạy được nữa.
1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?