선형 탐색 (C#)

📌 선형 탐색(Linear Search) 란?

선형 탐색(Linear Search)이란 배열이나 리스트와 같은 데이터 구조에서, 원하는 값을 찾기 위해 처음부터 끝까지 차례대로 검사하는 가장 기본적인 탐색 알고리즘이다. 선형 탐색은 정렬되지 않은 데이터에서도 사용할 수 있으며, 구현이 매우 간단하다.

 

• 말 그대로 처음부터 끝까지 하나씩 검사하는 방식이다.
• 정렬이 안 되어도 사용이 가능하다.
• 시간 복잡도는 O(n)이다.

구현 코드

// 인덱스를 찾아주는 선형탐색
static int LinearSearch(int[] arr, int target)
{
    // arr 원소 하나씩 확인 해 target과 일치하면 index를 반환
    for (int i = 0; i < arr.Length; i++)
        if (arr[i] == target)
            return i;

    return -1;
}

static void Main()
{
    int[] arr = { 78, 55, 45, 98, 13 };

    foreach (int p in arr)
    {
        Console.Write(p + " ");
    }

    Console.WriteLine();
    Console.WriteLine("찾을 숫자를 입력하세요");            
    string read = Console.ReadLine();
    int searchNum = int.Parse(read);
    int index = LinearSearch(arr, searchNum);
    
    if(index == -1)
        Console.WriteLine("찾는 숫자가 없습니다.");
    else
        Console.WriteLine($"원하는 숫자를 찾았습니다. 인덱스 = {index}");
}

 

결과