[Algorithm] 선형 탐색 알고리즘 에 대해 알아보자

---

선형 탐색

 

오늘 알아볼 것은 알고리즘의 기본 중의 기본 탐색 알고리즘에 대해 알아보고자 한다

많은 탐색 알고리즘 중 처음 배워 볼 것은 바로 선형 탐색 알고리즘이라고 하는 것이다.

 

선형 탐색 알고리즘 또는 순차 탐색 알고리즘이라고 하는 이것은

단어에서도 알 수 있듯이 특정한 무언가를 찾는 알고리즘이다

 

대상은 리스트, 배열과 같이 수가 나열되어 있는 곳이다

 

---

Big O 표기

 

선형 탐색 알고리즘의 시간 복잡도는 "O(N)"이며

이는 데이터의 량이 늘어날수록 아래 사진처럼

계산 시간도 같이 늘어나는 것을 의미한다.

 

이 처럼 검색 방법 중 가장 단순히 구현 가능하지만

검색할 대상의 리스트 길이가 길면 길수록 비효율적이게 된다.

 

---

스크립트

 

함수 로직

        static int LinearSearch(int[] arr, int target)
        {
            int idx = -1;

            for (int i = 0; i < arr.Length; ++i)
            {
                if (arr[i] == target)
                {
                    idx = i;
                    break;
                }
            }

            return idx;
        }

 

결과 출력

        static void Main(string[] args)
        {
            int[] arr = new int[]
            {
                9, 4, 7, 2, 1, 0, 6
            };

            int idx = LinearSearch(arr, 0);
            Console.WriteLine($"IDX : {idx}\n");
        }

 

---

레퍼런스 사이트

 

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%B0%A8_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

순차 검색 알고리즘 - 위키백과, 우리 모두의 백과사전