[Python] 검색 / 이진 검색(Binary search)

이진 검색

이진 검색이란, 정렬된 배열 내에서 지정된 입력값의 위치(key)를 찾습니다.
이진 검색은 입력값과 배열의 중간요소를 비교해서 입력값과 중간요소가 일치한다면 배열의 위치를 반환하고,
입력값이 중간요소보다 작다면 중간 요소의 왼쪽 하위 배열에서 검색 과정을 반복합니다. (정렬된 배열이므로)
큰 경우에는 요소의 오른쪽 하위 요소가 반복합니다.

이진 검색의 예시

[1, 2, 5, 6, 7, 10, 12, 13, 14, 15]라는 정렬된 리스트에서 13이란 값을 찾아보려고 합니다.

• 첫번째 실행
  시작 인덱스 0, 마지막 인덱스 9의 중간값 (0 + 9)//2 는 4이므로 인덱스 4의 값은 7입니다.
  13 > 7이므로 리스트의 오른쪽 요소에서 이진 검색을 실행합니다.
• 두번째 실행
  이전 실행에서 중간 인덱스는 4였으므로 시작 인덱스는 5, 마지막 인덱스는 9입니다.
  중간 인덱스는 (5 + 9)//2는 7이므로, 인덱스 7에 해당하는 값은 13 이므로 검색을 종료합니다.

이진 검색은 재귀 함수와 반복문을 사용하여 만들 수 있습니다.

재귀 함수를 이용한 이진 검색

def binary_search_rec(seq, target, low, high):

    if low > high:     # 예외 처리
        return

    mid = (low + high) // 2

    if seq[mid] == target:
        return mid
    elif seq[mid] < target:
        # mid값 보다 우측에 존재하므로
        return binary_search_rec(seq, target, mid + 1, high)
    else:
        # mid값 보다 좌측에 존재하므로
        return binary_search_rec(seq, target, low, mid - 1)

검색할 리스트 부분의 첫 인덱스를 low, 마지막 인덱스를 high라고 했을 때,
찾을 요소(target)가 중간 인덱스 mid보다 크다면 리스트의 우측에 있으므로 low에 (mid + 1)을 대입하여 재귀 호출,
mid보다 작다면 리스트의 좌측에 있으므로 high에 (mid - 1)을 대입하여 재귀 호출합니다.
함수를 반복하다 mid값이 찾을 요소와 같다면 해당 인덱스를 반환합니다.

반복문을 이용한 이진 검색

def binary_search_iter(seq, target):
    low = 0
    high = len(seq) - 1

    while low > high:     # 종료 조건
        mid = (low + high) // 2
        if seq[mid] == target:
            return mid
        elif seq[mid] < target:
            low = mid + 1        # 리스트 오른쪽으로 이동
        else:
            high = mid - 1       # 리스트 왼쪽으로 이동

• low, high 값을 바꿔주면서 검색할 리스트 부분을 이동하므로 low가 high보다 커지면 모두 검색한것이기 때문에 종료조건을 low > high로 합니다.
• 재귀함수와 마찬가지로 중간 인덱스 mid의 값과 찾을 요소(target)와 비교하여 보다 작다면 리스트의 오른쪽, 보다 크다면 리스트의 왼쪽으로 이동하며 반복하여 검색합니다.