LATEST

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán tìm kiếm tuyền tính (Linear Search) trong C / C++. Hay còn được gọi với cái tên khác là tìm kiếm tuần tự (sequential search).

Ví dụ: Mình có mảng Number = {2, 5, 8, 10, 22, 16, 8}. Giả sử mình muốn tìm số 5 có xuất hiện trong mảng hay không, nếu có thì nó nằm ở vị trí bao nhiêu.

Kết quả: Số 5 có xuất hiện trong mảng và nó nằm ở vị trí số 1 (vì mảng bắt đầu từ vị trí 0).

Vậy làm thế nào để viết thuật toán giải quyết vấn đề này, các bạn bắt đầu cùng mình thôi nhé.

Tìm kiếm tuyến tính là gì (Linear Search)?

Thuật toán tìm kiếm tuyến tính trong C / C++ là phương pháp tìm kiến một phần tử cho trước trong một danh sách nào đó. Phương pháp này hoạt động bằng cách duyệt qua từng phần tử trong danh sách để tìm ra giá trị mong muốn.

bai8 01 PNG

Như các bạn thấy trong hình, thì để tìm được giá trị J, cần phải duyệt qua từng phần tử trước đó để tìm. Nếu danh sách chúng ta có 1000 phần tử và phần tử đó nằm ở gần cuối thì việc tìm kiếm mất rất nhiều thời gian.

Vậy thuật toán tìm kiếm tuyến tính chỉ áp dụng cho những chương trình đơn giản. Các bạn lập trình viên mới bắt đầu học thì nên tìm hiểu về thuật toán tìm kiếm này.

Nếu trong trường hợp danh sách lớn thì chúng ta nên tìm một giải thuật khác tối ưu hơn và nhanh hơn nhé.

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Qua phần trên chắc các bạn cũng đã hiểu sơ qua về thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++ rồi đúng không ạ. Vậy hãy xem thuật toán tìm kiếm tuyến tính dưới đây nhé, mình sẽ giải thích ngay bên dưới.

int linearSearch(int arr[], int n, int x){
        //Lặp từng phần tử của mảng và kiểm tra.
    for(int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
        // Trả về -1 nếu đã duyệt hết mà ko tìm thấy.
    return -1;
}

Trong đó:

  • arr[] là mảng bao gồm các phần tử.
  • n là số lượng phần tử trong mảng.
  • x là giá trị cần tìm.

Giải thích thuật toán:

  1. Sử dụng vòng lặp for lặp từ 0 đến n - 1 (vì mảng bắt đầu từ 0 nên chúng ta phải lặp từ 0).
  2. Trong vòng lặp xét điều kiện nếu tồn tại giá trị a[i] = x thì trả về vị trí i của phần tử đó.

Bây giờ để hiểu rõ hơn, mình sẽ thực hiện một ví dụ tìm kiếm giá trị x có tồn tại trong mảng hay không nhé. Nếu có thì hiển thị vị trí của nó trong mảng. Chương trình sẽ được viết bằng hai ngôn ngữ C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>

int linearSearch(int arr[], int n, int x){
        //Lặp từng phần tử của mảng và kiểm tra.
    for(int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
        // Trả về -1 nếu đã duyệt hết mà ko tìm thấy.
    return -1;
}

int main(void) {
  int n,x, result;
    do{
      printf("Nhập vào số lượng phần tử của mảng: ");
      scanf("%d", &n);
      if(n <= 0) printf("Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n");
    }while(n <= 0);
    
    int a[n];
    //nhập các phần tử mảng
    for(int i=0; i<n; i++){
         printf("Nhập vào phần tử a[%d]: ",i);
         scanf("%d",&a[i]);
    }

    printf("Nhập giá trị x cần tìm: ");
    scanf("%d", &x);
    result = linearSearch(a, n, x);
    if(result == -1) printf("Không tìm thấy giá trị %d trong mảng.\n",x);
    else printf("Đã tìm thấy giá trị %d tại vị trí %d",x,result);

    printf("\n----------------------------\n");
    printf("Chương trình này được đăng tại codehow.net");
  return 0;
}

Kết quả:

bai8 03 PNG

Chương trình C++:

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int x){
        //Lặp từng phần tử của mảng và kiểm tra.
    for(int i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
        // Trả về -1 nếu đã duyệt hết mà ko tìm thấy.
    return -1;
}

int main() {
  int n,x, result;
    do{
      cout << "Nhập vào số lượng phần tử của mảng: ";
      cin >> n;
      if(n <= 0) cout<<"Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n";
    }while(n <= 0);
    
    int a[n];
    //nhập các phần tử mảng
    for(int i=0; i<n; i++){
         cout << "Nhập vào phần tử a[" << i << "]: ";
         cin >> a[i];
    }
    cout<<"Nhập giá trị x cần tìm: ";
    cin>>x;
    result = linearSearch(a, n, x);
    if(result == -1) cout<<"Không tìm thấy giá trị "<<x<<" trong mảng.\n";
    else cout<<"Đã tìm thấy giá trị "<<x<<" tại vị trí "<<result;

    cout<<"\n----------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

bai8 02 PNG

Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++. Ở bài tiếp theo mình sẽ giới thiệu các bạn một thuật toán tìm kiếm khác, đó là thuật toán gì thì hãy ghé thăm codehow.net nhé. Cảm ơn các bạn rất nhiều.

Cùng chuyên mục:

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy đuôi (Tail Recursion) trong C / C++

Đệ quy đuôi (Tail Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tìm ước chung lớn nhất trong C / C++

Thuật toán tìm ước chung lớn nhất trong C / C++

Top