이진 검색(Binary Search)

 

이진 탐색은 정렬된 데이터에서 특정한 값을 찾고자할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다.

 

2023.04.20 - [Data Structures & Algorithms] - 빅오 big-O

빅오 big-O

O(logN)의 설명은 이전의 글에서 간략하게 써둔 것이 있으니 참고해보자.. 부족한 설명으로 이해가 되지 않을 수 있으니.. 다른 포스팅을 보는 것이 효율적일 수도 있다. 나중에 수정할 예정이니 참고만 해보자. 아마도 코드로 구현해보면 어떤 식으로 효율적인지 알 수 있을 것이다.

 

 

 

 

오름차순으로 정렬된 배열에서 찾는 값은 66이라고 가정해보자.

 

1회전 중간 INDEX의 값 : 32 [10, 12, 31, 32, 42, 55, 66, 92]  => [10, 12, 31, 32, 42, 55, 66, 92]

 

loop1에서는 중간값이 찾는 값보다 작은 경우이다.

찾는 값이 중간값보다 크기 때문에 그 밑에 값들의 하한선 높인다.

 

2회전 중간 INDEX의 값 : 55 [10, 12, 31, 32, 42, 55, 66, 92]  => [42, 55, 66, 92]

 

loop2에서는 나머지 인덱스인 4,5,6,7의 중간값은 [5] 55이다.

여전히 찾는값인 66보다 작으므로 55부터 밑에 하한선을 높인다.

 

3회전 중간 INDEX의 값 : 66 [10, 12, 31, 32, 42, 55, 66, 92]  =>  [66, 92]

 

loop3에서는 인덱스의 중간값은 66이다. 찾는 값과 인덱스의 값이 같기때문에 인덱스를 반환한다.

 

이진검색을 파이썬 소스코드로 구현을 해보았다.

 

먼저 반복문으로 구현한 것이다.

def BinaryS(array,target):

    high = len(array)
    low = 0

    while(low <= high):
        mid = int((high + low) / 2)
        if (target == array[mid]):
            return mid
            
        elif (target >= array[mid]):
            low = mid +1
            
        elif (target <= array[mid]):
            high = mid -1
            
    return -1

 

소스코드를 살펴보자.

 

high = len(array)
low = 0

검색을 시작할 때는 target 값이 배열 어디든 있을 수 있으므로 low를 첫 번째 인덱스, high를 마지막 인덱스로 정한다.

 

 

실제로 검색은 while 루프  안에서 수행된다.

 

while(low <= high):

 

이 루프는 target 값을 찾을 수 있는 원소가 남아 있을 때까지 수행된다. 범위를 좁혀가다 보면 low <= high 절은 범위가 남아 있지 않는 상황에 도달하며 target 값이 배열에 없다고 판단 할 수 있다.

 

mid = int((high + low) / 2)
	if (target == array[mid]):
		return mid

 

mid 값은 범위 내 중간 지점에 있는 항목이다.

tartget 값이 찾고 있던 배열의 인덱스가 반환하는 값과 일치하면 mid 인덱스를 반환한다.

 

elif (target >= array[mid]):
	low = mid +1

 

target 값이 mid 값보다 크면 target은 mid보다 큰 위치에서만 찾을 수 있다. 그러므로 low 값을 이전의 mid + 1 값을 할당 해준다.

 

elif (target <= array[mid]):
	high = mid -1

 

target 값이 mid 보다 작으면 target 값은 mid 값보다 작은 위치에서만 찾을 수 있다. 그러므로 high 값을 이전의 mid - 1 값을 할당 해준다.

 

 return -1

 

루프를 전부 돌고난 후, 범위가 원소가 0개로 좁혀지면 target 값이 배열에 없다고 최종적으로 False를 반환한다.

 

 

재귀함수를 이용하여 구현할 수도 있다.

 

def BSearchRecursive(array,target,low,high):
    
    if (low > high): # 범위가 남아 있지 않다.
        return -1
    
    mid = int((low + high) / 2) # 중간인덱스를 선언

    if (array[mid] == target): # 타겟값과 중간값과 같다면
        return mid #중간 인덱스를 반환
        
    elif (array[mid] > target): # mid 값 보다 타겟값이 크다면
        return BSearchRecursive(array, target, low, mid-1) # 상한선을 줄여 다시 함수를 호출한다.
        
    else: # mid 값 보다 타겟값이 작다면
        return BSearchRecursive(array, target, mid+1, high)# 하한선을 줄여 다시 함수를 호출한다.

 

재귀함수를 통한 이진검색은 주석으로 따로 적어 표기해놓았다.