[알고리즘 algorithm] 이진 검색 Binary Search 정의와 사용 예제

이진 검색: 정렬된 배열에서 타겟을 찾는 검색 알고리즘.

시간복잡도가 O(logN)로 1억개의 데이터에서도 단 27번 안에 원하는 데이터를 찾아낼 수 있는 정말 마법같은 검색 알고리즘이다. 

 

이진탐색트리와 이진검색은 유사한 점이 많은데

이진탐색트리(BST)가 정렬된 구조를 저장하고 탐색하는 자료구조라면,

이진검색은 정렬된 배열에서 값을 찾아내는 알고리즘 자체를 지칭한다.

 

 

이진 검색 기본 문제: leetcode.com/problems/binary-search/

Binary Search - LeetCode

<재귀로 이진탐색 구현>

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        def bisect(left,right):
            if left <= right:
                mid = (left + right)//2
            
                if nums[mid] < target:
                    return bisect(mid+1, right)
                elif nums[mid] > target:
                    return bisect(left, mid-1)
                else:
                    return mid
            else:
                return -1
                
        return bisect(0,len(nums)-1)

<반복문으로 이진탐색 구현>

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = (left+right)//2
            
            if nums[mid]== target:
                return mid
            
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
         
        return -1

 

없는 숫자를 찾으면 어떻게 될까?

#lst가 홀수 개
lst = [1,2,3,4,5,6,7]

target = 2.5
left = 0
right = len(lst)-1
while left <= right:
    mid = (left+right)//2
    if lst[mid] == target:
        break
    elif lst[mid] < target:
        left = mid + 1
    else:
        right = mid - 1


print(left,right,mid)
>> 2 1 2

/////////////////////////////////////////

#lst가 짝수 개
lst = [1,2,3,4,5,6,7,8]

target = 2.5
left = 0
right = len(lst)-1
while left <= right:
    mid = (left+right)//2
    if lst[mid] == target:
        break
    elif lst[mid] < target:
        left = mid + 1
    else:
        right = mid - 1


print(left,right,mid)
>> 2 1 2

///////////////////////////////////////

lst = [1,2,3,4,5,6,7]

target = 3.5
left = 0
right = len(lst)-1
while left <= right:
    mid = (left+right)//2
    if lst[mid] == target:
        break
    elif lst[mid] < target:
        left = mid + 1
    else:
        right = mid - 1


print(left,right,mid)
3 2 2

실험 결과 mid값이 left, right 둘 중 하나를 랜덤으로 가리키게 된다. 

또한 left와 right는 서로 바뀌긴 하지만 정확한 범위를 짚고 있다.

따라서 (left+right) //2 를 한번 더 해주면 소수점이 나오긴 하지만 정확한 위치를 가리키게 된다.

 

 

 

파이썬에서는 이진 탐색 모듈을 제공하여 보다 쉽게 이진 탐색을 가능하게 한다.

위의 문제를 모듈을 이용하여 풀면 다음과 같다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        i = bisect.bisect_left(nums,target)
        if i < len(nums) and nums[i]==target:
            return i
        else:
            return -1

 

 

참고로 bisect는 target 값이 없으면 예상 위치의 인덱스를 찾아 반환한다. 예시를 보면 이해가 갈 것이다. 

from bisect import bisect_left
nums = [0,1,2,3,4,5]

target = 2
print(bisect_left(nums, target))
>> 2

target = 2.5
print(bisect_left(nums, target))
>> 3

target = 5
print(bisect_left(nums, target))
>> 5

target = 5.5
print(bisect_left(nums, target))
>> 6

 

 

출처:

<파이썬 알고리즘 인터뷰> 박상길 지음, 정진호 일러스트, 책만, 2020(https://www.onlybook.co.kr/entry/algorithm-interview)

 

*그외 참고사이트

https://yu5501.tistory.com/80