[CS] 이진탐색

 

 

이진탐색

 

정렬이 된 배열을 절반씩 줄여가면서 원하는 데이터를 탐색하는 기법

 

 

왜 이진탐색을 사용하나요?

 

이진탐색은 일반적인 탐색(순차적 탐색)보다 정렬된 배열 속에 데이터를 찾아내는 평균적인 시간복잡도가 유리하게 나타납니다.

 

예를 들면, 1부터 1억까지 정렬된 배열에서 1억을 찾아내라고 해보면, 일반적인 탐색은 1억번의 탐색을 진행해야 1억을 찾아낼 수 있지만,

 

이진탐색의 경우 절반씩 줄여나가서 탐색하기 때문에 log로 계산해보면 27번 탐색만에 1억을 찾아낼 수 있습니다.

 

아래 그림을 보며 쉽게 이해해보겠습니다.

 

 

위 그림을 보시면 1부터 100까지 정렬되어있는 배열에서 77을 찾아갈 때, 이진탐색으로 찾아가는 과정을 보여주고 있습니다.

 

100을 반으로 나누고, 찾고있는 77의 숫자를 살펴봅니다.

 

77은 50보다 크니 50이상인 오른쪽배열만 탐색하고 50미만인 왼쪽 배열은 탐색하지 않습니다.

 

50부터 100까지 또 반으로 갈라 75를 만듭니다. 찾고있는 77은 75보다 크니 75 이후 배열만 탐색합니다.

 

50부터 75미만 배열은 탐색하지 않습니다. 이런 과정을 재귀적으로 걸쳐 진행하여 77을 찾아낼 수 있습니다.

 

핵심은 특정 숫자를 찾을 때, 정렬된 배열을 반으로 쪼개고 왼쪽 배열과 오른쪽 배열 중 하나만 탐색을 진행한다는 점입니다.

 

 

 

 

파이썬을 사용하시는 분들은 아래 팁을 이용해보시면 좋을 것 같습니다.

 

파이썬에서는 이 이진탐색을 내장코드로 구현을 해놓았습니다.

def binary_search_builtin(nums, target):
    idx = bisect.bisect_left(nums, target)
		# idx == len(nums) 가능하기 떄문.
		"""Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if idx < len(nums) and nums[idx] == target:
        return idx
    else:
        return -1

 

bisect.bisect_left(nums, target) 이 코드가 파이썬에 내장코드입니다.

 

이 내장함수에 nums 배열과 target을 넘겨주면 이진 탐색을 진행합니다. 결과는 두가지 결과값 중 하나를 반환하는데,

 

먼저 결과 값을 찾았을 경우를 살펴보겠습니다.

 

조건은 두가지입니다. 찾아낸 target의 idx(인덱스)가 nums 배열을 넘어가지 않고

 

nums[idx]의 값에 실제 target값이 들어있으면 찾아낸 target의 인덱스를 반환하는 것입니다.

 

그 외 나머지 경우는 -1를 반환하여 target을 찾아내지 못한 결과를 반환합니다.