C# 탐색 알고리즘1 ( 선형탐색 / 이진탐색 )

1. 탐색 알고리즘(Search Algorithm)

탐색알고리즘이란 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공하는 것이다. 

 

1 ~ 10까지 나열된 숫자에서 6을 찾는 방법을 제공하는 것이 바로 탐색 알고리즘이다.

 

탐색 알고리즘도 종류가 여러가지 있는데 이번 포스트에서 다룰 내용은 선형탐색과 이진탐색이다.

 

1. 선형 탐색 (Linear Search)

선형 탐색은 탐색 알고리즘 중 가장 단순한 방법의 알고리즘으로 배열의 각 요소를 하나하나 차례대로 검사하여 원하는 항목을 찾는 방법이다.

 

김밥천국을 예를 들면 김밥천국에서 라면을 주문할 때 메뉴판을 보고 메뉴의 종류를 위에서부터 하나하나 찾아서 라면을 찾는 형식이 되겠다.

 

- 장점: 단순해서 구현하기가 쉽고, 정렬이 되어있지 않아도 상관없다.

- 단점: 앞이든 뒤든 하나하나 찾는것이기 때문에 검색시간이 오래걸린다.

 

선형탐색의 코드는 다음과 같다.

 

 
       public class Linear
       {
           public int Search(int[] arr, int target)
           {
               for(int i = 0; i < arr.Length; i++) 
               {
                   if (arr[i] == target)
                   {
                       return i;
                   }
               }
               return -1;
           }

       }

       static void Main(string[] args)
       {
           int[] arr = { 1, 3, 5, 6, 4, 9, 7, 10, 2, 8 };
           int target = 4;

           Linear linear = new Linear();

           int result = linear.Search(arr, target);

           Console.WriteLine($"수의 위치: {result}");

       }

 

배열과 찾을 숫자를 메서드에 전달하여  for문을 돌리고 배열에 담긴 수와 현재 찾는 수가 같으면 return해주는 식의 방법이다.

 

위와같이 배열이 정렬이 되지 않아도 찾을 수 있다.

 

 

2. 이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법이다. 중간을 딱 갈라서 타겟이 중간값보다 작으면 왼쪽을, 크면 오른쪽을 탐색하여 반을 계속 나눠 탐색하는 방법이다.

 

이는 실생활에서 숫자 1 ~ 100의 업다운 게임을 할 때 보통 50부터 시작해서 반을 계속 나눠 찾는 방식과 같다.

 

-장점: 반씩 나누면서 가기 때문에 속도가 빠르다.

-단점: 탐색하고자 하는 자료 구조안의 값들이 정렬되어있어야 한다.

 

이진 탐색의 코드는 다음과 같다.

 

        public class Binary
        {
            public int Search(int[] arr, int target)
            {
                int left = 0;
                int right = arr.Length - 1;

                while(left <= right)
                {
                    int mid = (left + right) / 2;

                    if (arr[mid] == target)
                    {
                        return mid;
                    }
                    else if (arr[mid] < target) 
                    {
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }

                }

                return -1;
            }
        }

        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            int target = 7;
            Binary binary = new Binary();

            int result = binary.Search(arr, target);

            Console.WriteLine($"수의 위치: {result}");

        }

 

탐색하고자 하는 수가 7이다. 왼쪽은 0 , 오른쪽은 9 가 되어 둘을 더하고 2로나누면 중간값이 된다. 그러면 값은 4가 들어오며 else if 문에 걸려 left는 4 + 1 인 5가 되어 5부터 9의 반을 또 나누고 반을 또 나눠서 7의 위치를 찾게 된다.