Home > Algorithm > Tìm kiếm tuyến tính – Linear Search

Tìm kiếm tuyến tính – Linear Search

1. Giới thiệu :

Trong khoa học máy tính, tìm kiếm tuyến tính ( linear search ) hay tìm kiếm tuần tự ( sequential search ) là phương pháp tìm kiếm một phần tử cho trước trong một danh sách ( list hoặc array ) bằng cách duyệt lần lượt từng phần tử của danh sách đó cho đến khi tìm thấy phần tử cần tìm hay đã duyệt qua toàn bộ danh sách.

2. Cài đặt :

/// <summary>
/// Thuật toán tìm kiếm tuyến tính trong 1 mảng
/// </summary>
/// <param name="value">Giá trị cần tìm</param>
/// <param name="arr">Mảng</param>
/// <returns>Vị trí của phần tử tìm thấy đầu tiên, trả về -1 nếu không tìm thấy</returns>
public int LinearSearch(int value, int[] arr)
{
    int length = arr.Length;
    int ret = -1;
    for (int i = 0; i < length; i++)
    {
        if (arr[i] == value)
        {
            ret = i;
            break;
        }
    }
    return ret;
 }

3. Đánh giá độ phức tạp thuật toán :

– Tốt nhất : O(1)  – Phần tử cần tìm ở vị trí đầu tiên

– Xấu nhất : O(n+1) – Phần tử cần tìm ở vị trí cuối cùng

– Trung bình : O(n) – Xác suất các phần tử trong danh sách chứa giá trị cần tìm là như nhau

Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: