linear search

1. Tìm Kiếm Tuyến Tính

Tìm kiếm là một công việc được thực hiện nhiều trong lập trình và trong thực tế, bạn có thể tìm kiếm trong dãy số hay trong danh sách sinh viên những sinh viên thỏa mãn điều kiện mong muốn.

Thuật toán tìm kiếm đơn giản nhất đó là thuật toán tìm kiếm tuyến tính - Linear search.

Giả sử bạn cần tìm kiếm xem phần tử X có xuất hiện trong mảng A[] hay không, ý tưởng của thuật toán rất đơn giản đó là duyệt tuần tự các phần tử trong mảng và so sánh giá trị cần tìm kiếm với các phần tử trong mảng.

Nếu gặp phần tử nào bằng phần tử X thì có thể kết luận tìm thấy, khi duyệt hết dãy số nhưng không tìm được giá trị X thì kết luận X không xuất hiện trong mảng.

Code : 

#include "stdio.h"

int linear_search(int a[], int n, int x){
    for(int i = 0; i < n; i++){
        if(a[i] == x){
            return 1; // tim thay
        }
    }
    return 0; // khong tim thay
}

int main(){
    int n = 10, x = 9;
    int a[10] = {3, 1, 2, 4, 5, 10, 9, 7, 8, 6};
    if(linear_search(a, n, x) == 1){
        printf("FOUND\n");
    }
    else{
        printf("NOT FOUND\n");
    }
    return 0;
}

Output : 

FOUND

Ngoài ra các biến thể của thuật toán tìm kiếm tuyến tính có thể kể đến như : Tìm vị trí đầu tiên (cuối cùng) của X trong mảng, đếm số lần xuất hiện của X trong mảng...

Code : Tìm vị trí đầu tiên của X trong mảng

#include "stdio.h"

int firstPos(int a[], int n, int x){
    for(int i = 0; i < n; i++){
        if(a[i] == x){
            return i;
        }
    }
    return -1; // khong tim thay
}

int main(){
    int n = 10, x = 3;
    int a[10] = {6, 1, 2, 4, 3, 10, 9, 3, 8, 6};
    if(firstPos(a, n, x) != -1){
        printf("Vi tri dau tien cua %d : %d\n", x, firstPos(a, n, x));
    }
    else{
        printf("NOT FOUND\n");
    }
    return 0;
}

Output : 

Vi tri dau tien cua 3 : 4

Code : Đếm số lần xuất hiện của X trong mảng

#include "stdio.h"

int count(int a[], int n, int x){
    int res = 0;
    for(int i = 0; i < n; i++){
        if(a[i] == x){
            ++res;
        }
    }
    return res;
}

int main(){
    int n = 10, x = 3;
    int a[10] = {6, 1, 2, 4, 3, 10, 9, 3, 8, 6};
    printf("So lan xuat hien cua %d : %d\n", x, count(a, n, x));
    return 0;
}

Output : 

So lan xuat hien cua 3 : 2