STDIO
Tìm kiếm gần đây
    • Nội dung
    • QR Code
    • 0
    • 0
    • Sao chép

    Linear Search - Tìm Kiếm Tuyến Tính

    Tìm hiểu về Linear Search - tìm kiếm tuyến tính qua code mẫu.
    15/08/2015
    17/08/2020
    2 phút đọc
    Linear Search - Tìm Kiếm Tuyến Tính

    Linear Search

    Linear search có các tên gọi khác như Sequential search – Tìm kiếm tuần tự  – Tìm kiếm tuyến tính là 1 trong các giải thuật hỗ trợ tìm kiếm 1 phần tử trong mảng.

    Ý tưởng

    Tìm kiếm từ đầu cho đến cuối mảng (hoặc ngược lại).

    • Nếu tìm thấy trả vị trí của kết quả tìm kiếm.
    • Nếu không tìm thấy thì trả về 1.
    Tìm kiếm tuyến tính - linear search

    Code mẫu Linear Search

    #include <iostream>
    using namespace std;
    
    int LinearSearch(int arr[], int numberOfElements, int key)
    {
        for (int i = 0; i < numberOfElements; i++)
            if (arr[i] == key)
                return i;
        return -1;
    }
    
    int main()
    {
        int arr[] = { 10, 8, 1, 21, 7, 32, 5, 11, 0 };
        int size = sizeof(arr) / sizeof(arr[0]);
    
        int index = LinearSearch(arr, size, 5);
    
        if (index == -1)
            cout << "Khong tim thay!" << endl;
        else
            cout << "Vi tri tim thay la: " << index << endl;
    
        return 0;
    }

    Output: Vi tri tim thay la: 6.

    Các bước thực hiện

    • Bước 1: Duyệt mảng từ vị trí đầu tiên i = 0.
    • Bước 2: Thực hiện so sánh arr[i]key. Nếu arr[i] == key trả về vị trí i.
      • Trong trường hợp này hàm sẽ trả về giá trị i = 6 do 7 nằm ở vị trí thứ 6.
    • Bước 3: Nếu duyệt hết mảng vẫn không tìm thấy thì trả về -1.

    Đánh giá

    • Trong trường hợp tốt nhất, phần tử cần tìm nằm ở vị trí đầu tiên, thuật toán sử dụng 1 lần so sánh.
    • Trong trường hợp xấu nhất, phần tử cần tìm nằm ở vị trí cuối hoặc không nằm trong mảng, thuật toán sử dụng n - 1 lần so sánh.
    • Linear Search là một giải thuật đơn giản khi hiện thực và khá hiệu quả với danh sách đủ nhỏ hoặc một danh sách chưa được sắp xếp.
    0
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào liên kết sản phẩm do STDIO đề xuất và mua hàng, STDIO có thể nhận được hoa hồng. Điều này hỗ trợ STDIO tạo thêm nhiều nội dung hữu ích.. Tìm hiểu thêm.

    Đề xuất

    Naive String Search - Tìm Kiếm Kiểu Thơ Ngây
    Hướng dẫn tìm kiếm một chuỗi kí tự trong một đoạn văn bản bằng giải ...
    Thuật toán Depth First Search
    Giới thiệu, khái quát, trình bày và cung cấp code mẫu về thuật toán ...

    Khám phá

    Thuật toán Breadth First Search
    Giới thiệu, khái quát, trình bày và cung cấp code mẫu về thuật toán ...
    Phần 1 - Cây Nhị Phân Tìm Kiếm
    Các thao tác trên cây nhị phân tìm kiếm - khởi tạo, chèn, tìm kiếm, ...
    Giải Thuật Tìm Kiếm Minimax
    Giải thuật Minimax là một thuật toán đệ quy lựa chọn bước đi kế tiếp ...
    Các Giải Thuật Lập Trình Kinh Điển Với C++
    Code mẫu các giải thuật tìm kiếm, sắp xếp, lý thuyết đồ thị với C/C++.
    Dropshipping là gì?
    Tìm hiểu về dropshipping, mô hình thương mại thời hiện đại và giải đáp ...
    Vì Sao Sinh Viên Ngành Khoa Học Máy Tính Học C++ Như 1 Ngôn Ngữ Chính?
    Vì sao sinh viên ngành Khoa Học Máy Tính nên xem và học C++ như một ngôn ...
    Affiliate Marketing là gì?
    Tìm hiểu về cách thu lợi từ cộng đồng của bản thân đã gầy dựng và phát ...
    Thuật Giải A*
    Giới thiệu và hướng dẫn hiện thực thuật giải A* - A-star tìm kiếm đường ...
    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    developer@stdio.vn

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020