STDIO
Tìm kiếm gần đây

    Nội dung

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

    15/08/2015
    06/04/2017
    Tìm kiếm là một nhu cầu thiết yếu trong cuộc sống, và đương nhiên, cũng không phải là ngoại lệ trong lập trình. Tôi sẽ bắt đầu với thuật toán tìm kiếm đơn giản nhất: Sequential search – Tìm kiếm tuần tự hay Linear search – Tìm kiếm tuyến tính.

    Giới thiệu

    Tìm kiếm là một nhu cầu thiết yếu trong cuộc sống, và đương nhiên, cũng không phải là ngoại lệ trong lập trình. Chúng ta có rất nhiều thuật toán để thực hiện thao tác tìm kiếm. Để mở đầu cho chuỗi bài viết về các thuật toán tìm kiếm, tôi sẽ bắt đầu với thuật toán tìm kiếm đơn giản nhất Sequential search – Tìm kiếm tuần tự hay Linear search – Tìm kiếm tuyến tính.

    Linear Search

    Ý tưởng

    Bạn hãy tưởng tượng rằng, bạn có một chiếc chìa khóa và một tập hợp các ổ khóa. Nhiệm vụ của bạn là phải kiếm xem có hay không ổ khóa vừa chiếc chìa khóa trên tay. Cách đơn giản nhất đó là, chúng ta sẽ thử chiếc chìa khóa với từng ổ khóa cho tới khi nhận được kết quả.

    ss_1

    Hiện thực

    void LinearSearch(int arr[], int numberOfElements, int key)
    {
    	int index = 0;
    	bool isKeyFound = false;
    	
    	for (index; index < numberOfElements; index++)
    	{
    		if(arr[index] == key)
    		{
    			printf("%d is found at index %d\n", key, index);
    			isKeyFound = true;
    		}
    	}
    
    	if (index == numberOfElements && isKeyFound == false)
    		printf("There is no %d in array.\n", key);
    }

    Ở đây, tôi đưa ra một mảng arr gồm 9 phần tử, và cần tìm kiếm phần tử có giá trị key = 5 trong mảng này.

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

    • Bước 1: Duyệt mảng từ vị trí đầu tiên - index = 0.
    • Bước 2: Thực hiện so sánh arr[index] và key. Nếu arr[index] == key thì in ra dòng chữ xác nhận tìm thấy key và in ra vị trí tìm thấy (index). Đồng thời bật cờ isKeyFound để đánh dấu trong mảng có ít nhất 1 vị trí tồn tại key.
    • Bước 3: Nếu index == numberOfElements tức đã duyệt mảng xong và isKeyFound == false (mảng không tìm thấy vị trí nào chứa key), thì in ra thông báo trong mảng không tồn tại key.

    Đá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 thuộc 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 đơn giản.

    Bạn có thể download mã nguồn và tham khảo thêm các giải thuật tìm kiếm hữu ích khác theo đường dẫn.

    Bài viết liên quan

    Thuật toán Depth First Search

    Thuật toán Depth First Search - DFS (tìm kiếm theo chiều sâu) cùng với Thuật toán Breadth First Search - BFS là một trong hai thuật toán tìm kiếm cơ bản trong bộ môn Trí ...

    Trần Minh Thắng19/09/2015

    Thuật toán Breadth First Search

    Thuật toán Breadth First Search (Tìm kiếm theo chiều rộng) cùng với Thuật toán Depth First Search là một trong hai thuật toán tìm kiếm cơ bản trong bộ môn Trí tuệ nhân ...

    Trần Minh Thắng19/09/2015

    Naive String Search - Tìm Kiếm Kiểu Thơ Ngây

    Trong những giải thuật tìm kiếm đa số đều sử dụng nhiều cho các mảng có các phần tử là số. Trong bài viết này và một số bài viết sau, tôi sẽ giới thiệu thêm về các giải ...

    Trương Diễm Hương16/08/2015

    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, duyệt cây với C/C++.

    Nguyễn Đăng Khánh01/02/2016

    7 Điều Không Nên Bỏ Qua Trước Khi Tham Gia Phỏng Vấn Kỹ Thuật

    Với hơn 7 năm kinh nghiệm trong lĩnh vực đào tạo và tuyển dụng Lập Trình Viên, tôi nhận thấy các ứng viên khi đi phỏng vấn tìm việc mắc rất nhiều sai lầm không đáng có, ...

    Lê Minh Tài12/08/2015

    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 trong một trò chơi có hai người bằng cách định giá trị cho các Node trên cây trò chơi sau đó tìm Node ...

    ShichiKi Lê07/12/2015

    Hành Trình Nghiên Cứu: Khảo Sát Về Hướng Nghiên Cứu

    Khi bắt đầu bất kỳ một hướng nghiên cứu nào cũng cần có một cuộc khảo sát về tình hình thực tế. Sau thời gian 3 tháng làm việc trong môi trường nghiên cứu chuyên nghiệp, ...

    Kanzaki Nguyen15/08/2015

    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++.

    STDIO Training30/06/2020

    Hành Trình Của Một Gói Tin

    Cách một gói tin được tạo ra và truyền đi trên mạng Internet, tìm hiểu cách thức hoạt động của một số giao thức thông dụng. Bài viết là những kiến thức, kinh nghiệm mà ...

    Phi Phạm15/04/2015

    Smart Home – Từ Rời Rạc Hóa đến Tổng Thể Thông Minh

    Từ những thiết bị vốn được tạo ra tự động một cách rời rạc đến kết nối thành một tổng thể thông minh. "Với cái bóng đèn mình vỗ tay một cái thì nó sáng bóng đèn, vỗ hai ...

    Tal Tal28/03/2016

    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
    [email protected]

    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