이분 탐색(Binary Search)

Binary는 호남선으로 알고있는 사람들이 많지만 사실 Binary는 2진법을 의미한다.

이분 탐색(Binary Search)
이분 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

구현

이분 탐색을 구현하기 위해서는 다음과 같은 알고리즘이 필요하다.

• 배열을 정렬한다.(sort)
• 정렬된 배열에서 왼쪽 끝 인덱스 low와 오른쪽 끝 인덱스 high을 이용해 중간 인덱스 mid 값을 찾는다.
• mid 인덱스와 배열에서 찾고자 하는 값 target을 비교한다.
• target이 나올 때까지 탐색 과정을 반복한다.
• mid 값보다 target이 크다면 low를 mid+1로 이동시켜, 오른쪽 구간에서 탐색한다.
• mid 값보다 target이 작다면 high을 mid-1로 이동시켜, 왼쪽 구간에서 탐색한다.
• target이 없다면, False을 반환한다.

위의 과정을 반복과 재귀를 사용하여 모두 구현할 수 있다.

재귀

def binarySearch(array, target, 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

반복 

def binary_search(array, target):
    array.sort()
    
    low = 0
    high = len(array)-1
    
    while low <= high:
        mid = (low + high)//2 
        if array[mid] == target: 
            return mid 
        elif array[mid] > target: 
            high = mid-1 
        else: 
            low = mid+1
    
    return False

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 데이터 N개가 있을 때, 한 번 확인할 때마다, 탐색의 범위가 절반씩 줄어들어, 탐색해야할 데이터가 N/2, N/4...으로 줄어들게 된다. 즉 이분 탐색의 시간 복잡도는 O(logn)이 된다.

문제 1

처음 위 문제를 보았을 때 반복문을 이용해 숫자가 존재 하는지 찾으려 했다. 하지만 결과는..

때문에 시간 복잡도가 O(logn)인 이진 탐색으로 다시 접근 하였고 다음과 같은 풀이로 문제를 풀 수 있었다.

Solution

N = int(input())
result = []
arr1 = list(map(int, input().split()))
M = int(input())
arr2 = list(map(int, input().split()))
arr1.sort()

def binarysearch(arr, x):
    low = 0
    high = len(arr) -1

    while low <= high:
        mid = (low+high)//2
        if x == arr[mid]:
            print(1)
            return True
        elif x > arr[mid]:
            low = mid + 1
        else:
            high = mid -1
    print(0)
    return False

for i in range(M):
    binarysearch(arr1, arr2[i])

이 외 많은 시간 초과로 해결 할 수 없던 문제들을 이분 탐색으로 쉽게 해결 할 수 있게 되었고, 알고리즘의 실행 시간도 많이 단축 되었다. 앞으로 시간 초과가 날 것 같은 문제들은 이분탐색을 고려해 보는것이 좋을 거 같다!