이진 탐색 [Algorithm #3]

데이터를 탐색하는 기본적인 방법은 순차 탐색이다.

 

순차 탐색(Sequential Search)

특정 데이터를 찾기 위해서 맨 앞에서부터 하나씩 체크하는 탐색 방법이다. for문을 이용하여 리스트 내 원소를 찾는 것도 순차 탐색의 일종이다.

 

무조건 찾을 수 있다는 보장이 주어지지만, 최악의 경우 시간 복잡도가 O(N)으로 오래 걸릴 수 있다.

 

이진 탐색(Binary Search)

데이터가 정렬되어 있음이 보장되어 있을 때, 이진 탐색 알고리즘을 사용할 수 있다. 탐색 범위를 절반씩 좁혀가며 탐색하는 특징을 가지고 있다. 이진 탐색의 시간 복잡도는 절반씩 줄어드므로 O(logN)이다. 

 

예를 들어 오름차순으로 정렬된 숫자 리스트에서 숫자 20을 찾고 싶다면, 시작 START : 중간 MIDDLE : 끝 END의 총 3개 Index를 정해둔 뒤, 리스트[MIDDLE] 가 20보다 크면 20은 MIDDLE보다 왼쪽 범위에 있고, 20보다 작으면 오른쪽 범위에 있다. 이렇게 하면 범위를 절반씩 좁혀가며 원하는 값을 찾을 수 있다.

 

def binary_search(array,target,start,end):
	while start<= end: # 범위 내 반복.
    	mid = (start+end)//2 # 
        if array[mid] == target: # target을 찾은 경우.
        	return mid
        elif array[mid] > target: # mid 왼쪽 범위
        	end = mid - 1
        else: # mid 오른쪽 범위
        	start = mid + 1
    return None

n,target = list(map(int,input().split()))
array = list(map(int, input().split()))

result = binary_search(array,target,0,n-1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

 

구현이 어렵긴 하지만 높은 난이도 문제에서 많이 사용되기 때문에 코드를 자주 써서 익숙해지는 수밖에..