[algo] 이진탐색이란?

이진탐색

정렬되어 있는 배열에서 데이터를 찾으려고 시도할 때, 탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법

이분탐색(이진탐색/binary search)의 기본조건은
원소가 오름차순이나 내림차순으로 정렬된 배열에서 사용 가능하다는 것!

이진탐색의 시간복잡도 및 빅오 표기

O(logN)

N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8, … , 1 으로 실행됨. 여기서 실행된 탐색의 횟수가 시간 복잡도가 될 것이고 그 값을 K라고 한다면

1에 2를 K번 곱하면? N이 된다.
2^K = N
K = log2N

즉, 이진 탐색의 시간 복잡도는 O(logN) 이 된다.

구현 위한 준비

target : 찾고자 하는 값
data : 오름차순(내림차순)으로 정렬된 list
start : data 의 처음 값 인덱스 (여기서 인덱스라는 게 핵심)
end : data 의 마지막 값 인덱스
mid : start, end 의 중간 인덱스

구현 개요

자료의 중간 값이 (mid) 찾고자 하는 값인지 검사
아니라면 대소관계를 비교하여 start, end 값 이동
동일 연산 반복 (재귀로 구현 가능)

코드로 표현

data 중에서 target을 검색하여 맞으면 index 값을 return
없으면 None을 리턴

1. while start <= end:

# 바이너리 서치
# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

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

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다 // 타겟이 있으면 인덱스 리턴
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None # 타겟이 없으면 while문을 빠져 나오므로 None을 리턴

# 테스트용 코드
if __name__ == "__main__":
  li = [i**2 for i in range(11)]
  target = 9
  idx = binary_search(target, li)

  if idx:
      print(li[idx])
  else:
      print("찾으시는 타겟 {}가 없습니다".format(target))

2. 재귀적 구현

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:  # 타겟이 없으면 None을 리턴 (재귀 종료 조건)
        return None 

    mid = (start + end) // 2

    if data[mid] == target:
        return mid # 타겟이 있으면 인덱스 리턴
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data) # 함수 내에서 start, end 조정해준 다음 해당 값을 똑같이 호출해줌

# 테스트용 코드
if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

Sources

https://wayhome25.github.io/cs/2017/04/15/cs-16/
https://cjh5414.github.io/binary-search/