이분탐색/이진탐색/Binary Search

이분 탐색이 무엇인가?

정렬된 리스트에서 탐색 범위를 반씩 좁혀가며 특정 값을 찾는 탐색 알고리즘

 

시간 복잡도는 어떻게 되는가?

순서대로 탐색하는 순차탐색의 시간복잡도는 O(N)

범위를 반씩 좁혀가며 탐색하므로 순차탐색보다 작은 O(logN)의 시간복잡도를 가진다

 

언제 써야 하지?

정렬된 리스트에서 특정값이 처음 등장하는 위치를 찾을 때

 

Lower Bound, Upper Bound는 뭐지?

Lower Bound는 현재 탐색 범위에서 가장 작은 값의 위치,

Upper Bound는 현재 탐색 범위에서 가장 큰 값의 위치이다

 

예를들어 정렬된 배열 arr={1, 2, 3, 4, 5}가 있을때

Lower Bound는 최솟값인 1이 위치한 인덱스 0을 말하고

Upper Bound는 최댓값인 5가 위치한 인덱스 4를 말한다

 

이분탐색은 탐색범위를 반씩 좁혀야 하므로 Lower Bound와 Upper Bound 이외에  또 다른 변수 mid를 사용한다

mid는 탐색할 리스트의 중간 값으로 (Lower Bound+UpperBound)/2이고

arr에서 mid는 인덱스 2를 말한다

 

만약 찾는 값이 arr[mid] 값인 3보다 크다면 Lower Bound를 mid+1(3)로 변경해줘서 탐색 범위를 절반으로 좁힌다

만약 찾는 값이 arr[mid] 값인 3보다 작다면 Upper Bound를 mid-1(1)로 변경해줘서 탐색 범위를 절반으로 좁힌다

 

이분탐색에서는 위의 과정을 반복하다가 

찾는 값이 arr[mid] 값과 같으면 그때의 mid 값을 반환한다

 

이분탐색 구현하기

위의 리스트 arr에 대해 이분탐색을 진행할 수 있는 코드이다

찾는 값이 리스트의 최솟값보다 작거나 최댓값보다 크면 찾을 수 없다고 출력한다

그렇지 않으면 찾는 값이 리스트에 존재하는지 탐색을 시작한다

lowerBound와 upperBound가 리스트의 인덱스 범위를 벗어나지 않도록 범위를 한정하는 게 중요하다

인덱스 범위를 벗어나거나 찾는 값의 인덱스를 찾으면 반복문을 종료한다

using System;

namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 1, 2, 3, 4, 5 };

            int lowerBound = 0;
            int upperBound = arr.Length-1;
            int mid = (lowerBound + upperBound) / 2; ;

            int searchNum=int.Parse(Console.ReadLine());

            if (searchNum < arr[lowerBound] || searchNum > arr[upperBound])
                Console.WriteLine("{0}을 찾을 수 없습니다", searchNum);
            else
            {
                while (lowerBound >= 0 && upperBound <= arr.Length - 1)
                {
                    if (searchNum > arr[mid])
                        lowerBound = mid + 1;

                    if (searchNum < arr[mid])
                        upperBound = mid - 1;
 
                    mid = (lowerBound + upperBound) / 2;

                    if (searchNum == arr[mid])
                        break;
                }   
                Console.WriteLine("{0}의 index: {1}", searchNum, mid);
            }
        }
    }
}

2를 찾는 경우

6을 찾는 경우