[Python] 이진 탐색

탐색

- 순차 탐색

데이터를 앞에서부터 순서대로 확인

최악의 경우 시간 복잡도 O(N)

- 이진 탐색

데이터가 정렬이 되어있을 때 사용할 수 있지만 빠르게 찾을 수 있다.

시작점, 끝점, 중간점이 필요

시간 복잡도 O(logN)

 

탐색이 많은 문제에서 sort()를 하고 이진 탐색을 이용하는 방법이 있습니다

 

---

이진 탐색 구현

data =[0,2,4,6,8,10,12,14,16,18]

 

 

재귀 함수를 이용한 이진 탐색 코드

def binary_search(array, target, start, end):
    if start > end: # start, mid, end 다 같을 때 mid+1이나 mid-1하면 start>end가 됨
        return None
    
    mid = (start + end)//2
    
    if array[mid] == target:
        return array
    else:
        # target이 더 작음(왼쪽으로 가야함)
        if array[mid] > target:
            binary_search(array, target, start, mid-1)
        # target이 더 큼(오른쪽으로 가야함)
        else:
            binary_search(array, target, mid+1, end)
            
start = 0
end = len(data)-1
target = 100
print(binary_search(data, target, start, end))

 

 

반복문을 이용한 이진 탐색 코드

def binary_search(array, start, end, target):
    while start <= end:
        mid = (start+end)//2
        
        if array[mid] == target:
            return mid
        else:
            # target이 더 작음(왼쪽으로 가야함)
            if array[mid] > target:
                end = mid-1
            # target이 더 큼(오른쪽으로 가야함)
            else:
                start = mid+1
    return None           
    
start = 0
end = len(data)-1
target = 100
print(binary_search(data, start, end, target))

 

 

사실 시간을 좀 더 줄이기 위해 start와 end와 비교하는 코드도 넣었습니다

def binary_search(array, start, end, target):
    while start <= end:
        mid = (start+end)//2
        if array[start] == target:
            return start 
        elif array[end] == target:
            return end
        elif array[mid] == target:
            return mid
        else:
            # target이 더 작음(왼쪽으로 가야함)
            if array[mid] > target:
                end = mid-1
            # target이 더 큼(오른쪽으로 가야함)
            else:
                start = mid+1
    return None        
    
start = 0
end = len(data)-1
target = 100
print(binary_search(data, start, end, target))