이진 탐색은 검색 알고리즘 중 하나로, 오름차순으로 정렬되어 있는 배열에서 값을 찾기 위해 중간 값을 기준으로 가능성을 반씩 줄여 target value를 탐색하는 알고리즘이다.

개념

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. (참고: 위키백과)

예제

재귀함수를 사용한 이진탐색 함수다. 어쩐지 뭔가 반복문처럼 Return을 인자만 바꾼 자기 자신을 해서 신기하다고 생각했는데, 이름이 따로 있었다. 재귀함수 외에도 반복문을 통해서 구할 수 있다.

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) / 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

- 입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

5
4 1 5 2 3
5
1 3 7 9 5

- 출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

1
1
0
0
1

- 정답

문제를 이해하는데 시간이 조금 걸렸는데, N은 내가 숫자가 있는지 여부를 확인해줄 정답 배열의 길이, 그 다음 줄은 1부터 N까지의 숫자가 랜덤으로 있는 배열이다.

그리고 M은 내가 있는지 여부를 확인할 문제들이 모여있는 배열이고, 반복문을 돌려서 정답 배열 안에 있는지 확인할 숫자 들이다.

아래 코드를 보면 결과적으로 정답 배열을 sorted 함수로 오름차순 정렬해준 다음, 문제 배열을 이진탐색으로 돌려서 결과를 프린트한다.

신기한게 함수를 Return하면서 정의한 변수를 인자로 넣는 형태로 반복문처럼 돌리게 된다. 아니면 while True를 써도 될 것 같다.

def BinarySearch(arr, val, low, high):
    if low > high:
        return False
    
    mid = (low + high) // 2
    if arr[mid] > val:
        return BinarySearch(arr, val, low, mid - 1)
    elif arr[mid] < val:
        return BinarySearch(arr, val, mid + 1, high)
    else:
        return True

N = int(input())
A = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))
A = sorted(A)     

for m in M_list:
    if BinarySearch(A, m, 0, N-1):
        print(1)
    else:
        print(0)

시간복잡도

매 시행마다 검색할 자료의 수가 1/2씩 줄어든다는 특징이 있다. 자료의 개수 N에서 계속 1/2을 곱하는 형식을 하다보면 최종적으로 k번했을 때 아래와 같이 남은 자료의 수가 1이 되는 식이 나온다.

이 때 우리가 구해야 하는 것은 k값이기 때문에, 양변에 2의 k승을 곱하고 로그를 취해주면 다음과 같이 k는 log2N이 된다.

결과적으로 자료 N개에 대한 이진 탐색의 시간복잡도는 BigO 표기법으로 다음과 같다. Big O 표기법에서 상수는 무시하기 때문에 2는 제외하고 log만 쓰여졌다)

- Big O표기법

위키백과에는 너무 어렵게 써져있어서 링크를 참고했다. 다른 말로 점근 표기법이라고도 한다.

"실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미인 점근적 표기법 형태를 사용하는 것이 편리할 수도 있습니다. 이런 경우를 위해 "big-O" 표기법을 사용합니다.

big-O는 알고리즘의 효율성을 나타내는 지표입니다. big-O를 이용하여 내가 개선한 알고리즘이 빨라졌는지, 메모리를 많이 잡아 먹지는 않는지 등의 알고리즘의 성능을 판단합니다. 시간에 대한 개념인 시간 복잡도와 공간에 대한 공간 복잡도가 있습니다. (참고: 링크)

그나마 쉽게 설명되어 있는 링크를 가져와봤다.

시간복잡도 비교

경우에 따라서 정확한 시간복잡도를 구하는 게 어려울 수 있다. 이에 가장 차수가 높은 것만 남겨놓아 비교하는 빅오 표기법이다. 차수가 높은 n이 처리할 데이터가 많을수록 그 차이가 크기 때문이다.

T(n)=n5+n3+n+5 => O(n)=n5

빅오 표기법은 식을 단순화하는 것보다 "알고리즘을 수행시간에 따른 성능 기준을 나누기 쉽다"에 의미가 있다. 정확한 식을 모르더라도 "이 알고리즘의 성능은 여기 정도다"라고 판단할 수 있기 때문이다. 다음은 기준으로 자주 사용되는 빅오 표기다.

• O(1) : 상수시간(Constant Time)
• O(logn) : 로그시간 또는 대수시간(Logarithmic)
• O(n) : 선형시간(Linear)
• O(nlogn) : 로그선형시간(Log-Linear)
• O(n2) : 제곱시간(Quadratic)
• O(n3) : 세제곱시간(Cubic)
• O(2n) : 지수시간(Exponential)
  ** 마크다운에서 제곱 표시가 안 되어서 n2, n3, 2n으로 표시했으나 실제로는 제곱 표시되어야됨!

직접 그래프는 https://www.desmos.com/calculator 에서 그려볼 수 있다. 2n을 제외하면 초반부에 O(1)보다 더 좋은 성능처럼 그래프에 나오지만, 실제로 데이터 처리는 개수가 1부터 시작이므로 의미가 없다.

logn의 성능이 굉장히 좋은 것을 알 수 있는데 이게 바로 이진 탐색!