이진 탐색 알고리즘이란

이진 탐색 알고리즘이란?

 

  프로그래밍에서 이진 탐색 알고리즘이란, 특정 범위안에서 찾아야할 대상이 있을 때 범위를 1/2씩 좁혀가며 탐색의 실행하는 알고리즘이다.

 

 아래 이미지를 보면 이해하기 쉬운데 77을 찾기 위해 1부터 차례대로 검색을 하게되면 77번 연산을 실행해야 하지만 1~100 사이의 중간값 부터 77까지의 차이를 비교하여 계속 범위를 절반으로 좁혀가다 보면 6번의 연산으로 77에 도달할 수 있다. 

 

나무위키에서 가져온 이미지

 

 이 때, 연산이 한번 진행될 때 마다 탐색 범위가 절반씩 줄어드는 것을 확인할 수 있는데, 이것을 시간 복잡도로 나타낸다면 O(logN)이 된다. (시간 복잡도란 입력 값이 N일 때 실제 소요되는 시간)

 

 이것을 프로그램언어로 구현하기 위해 Lower Bound와 Upper Bound의 개념을 사용한다. Lower Bound는 탐색할 배열의 첫번째 인덱스(0)이며, 반대로 Upper Bound는 배열의 가장 끝(arr.Length - 1)이다. 이떄, 원하는 값을 찾기 위해 mid(배열의 중간값)가 필요한데 찾는 값이 mid보다 크면 Lower Bound에 mid의 값을 저장하여 범위를 줄이며, 반대로 찾는 값이 mid보다 클 작을 경우 Upper Bound에 mid의 값을 저장하여 범위를 줄인다.(이 기능을 사용하기위해 범위의 배열은 반드시 정렬되어 있어야 한다.) 

 

 아래 C#을 통해 해당 기능을 구현해 보았다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace _230127_1
{
    class Program
    {
        static void Main(string[] args)
        {
            // 1부터 100을 저장하는 정수형 배열을 값으로 갖는 변수 정의
            int[] arr = new int[100];
            for(int i = 0; i < 100; i++) 
            {
                arr[i] = i + 1;
            }
                        
            int lo = 0;
            int hi = arr.Length - 1;            
            int goal = 77;
            int cnt = 0;

            while (true)
            {
                int mid = (hi + lo) / 2; //lo와 hi의 중간 값을 구하는 식

                if (arr[lo] + 1 == goal) break; //lo가 목표에 도달할 때 까지 연산

                if (arr[mid] < goal) // mid가 목표보다 작으면 lo에 mid 값을 저장
                {
                    lo = mid;
                    cnt++;
                    Console.WriteLine("{0}번째 반복, 목표 : {1}", cnt, goal);
                    Console.WriteLine("현재 low 값은 : {0}", arr[lo]);
                    Console.WriteLine("현재 high 값은 : {0}", arr[hi]);
                }
                else if (arr[mid] > goal) // mid가 목표보다 크다면 hi에 mid 값을 저장
                {
                    hi = mid;
                    cnt++;
                    Console.WriteLine("{0}번째 반복, 목표 : {1}", cnt, goal);
                    Console.WriteLine("현재 low 값은 : {0}", arr[lo]);
                    Console.WriteLine("현재 high 값은 : {0}", arr[hi]);
                }

                Console.WriteLine();
            }

            Console.WriteLine("총 {0}회 반복, 목표 : {1}", cnt, goal);
            Console.WriteLine("최종 low 값은 : {0}", arr[lo]);
            Console.WriteLine("최종 high 값은 : {0}", arr[hi]);
        }
    }
}

 

 

최종 목표값이 low와 high의 사이에 위치한 것을 확인할 수 있다.