[알고리즘/Python] 이분탐색

이분탐색 Binary Search

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식

• 탐색은 오름차순 정렬된 상태로 해야 한다.

시간복잡도

• 전체 탐색 : O(N)

• 이분 탐색 : O(logN)

작동 방식

1. 데이터 정렬

2. 데이터의 중간값(mid)이 찾고자 하는 값(target)인지 비교

3. mid 값이 target 값과 다르면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복

   • target < mid : end를 mid 왼쪽 값으로 바꾼다. (중간값 기준 왼쪽 부분 탐색)

   • target > mid : start를 mid 오른쪽 값으로 바꾼다. (중간값 기준 오른족 탐색)

# 반복문 활용
def binary_search(target, data):
    data.sort()
    start = 0 # 맨 처음 위치
    end = len(data) - 1 # 맨 마지막 위치

    while start <= end:
        mid = (start + end) // 2 # 중간값
        
        if data[mid] == targe:
            return mid
        elif data[mid] > target: # target이 작으면 왼쪽을 더 탐색
            end = mid - 1 
        else: # target이 크면 오른쪽을 더 탐색
            start = mid + 1
    return

# 재귀 활용
def binary_search(target, start, end):
    if start > end: # 범위를 넘어도 찾지 못하면 -1 반환
        return -1

     mid = (start + end) // 2

     if data[mid] == target:
         return mid
     elif data[mid] > target:
         end = mid - 1
     else:
         start = mid + 1
     return binary_search(target, start, end) # 줄어든 범위를 계속해서 탐색

def solution(target, data):
     data.sort()
     start = 0
     end = len(data) - 1
     return binary_search(target, start, end)