이진 탐색의 기초

0. 이진 탐색이란

1. 구현

• 주요 항목들
  1) target = 검색 목표
  2) list = 오름차순 정렬된 목록
  3) start = list의 처음 값 인덱스
  4) end = list의 마지막 값 인덱스
  5) mid = list의 중간 값 인덱스
• 구현 개요
  1) mid가 target인지 검사한다.
  2) 아니라면 둘을 대소비교하여 start 혹은 end의 값을 이동한다.

# 방법 1.
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
        
# 방법 2. 재귀
def binary_search_recursion(target, start, end, data):
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    if data[mid] == target:
        return mid
    elif data[mid] < target:
        start = mid + 1
    else:
        end = mid - 1
    
    return binary_search_recursion(target, start, end, data)

참고 링크
[노마드 코더] Binary Search vs. Linear Search Algorithm