이진 탐색 (Binary Search)

이진 탐색이란?

• 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만(오름차순) 사용할 수 있는 알고리즘이다.
• 변수 3개를 사용하여 탐색한다.(start, end, mid) 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

이진 탐색의 과정

• 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교함
• mid값이 target과 다르다면 대소관계를 비교하여 탐색범위를 좁히고, target과 mid값이 같을 때까지 반복함
  • 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] == target:
            return mid 		# target 위치 반환

        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:	# 중간값의 데이터가 target과 같다면 mid를 반환
        return mid 

    elif data[mid] > target: # target이 작으면 왼쪽 탐색
        end = mid - 1
    else:                    # target이 크면 오른쪽 탐색
        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)

이진 탐색의 특징

• 시간 복잡도는 탐색 범위를 반으로 나누는것과 동일하므로 O(logN)임 -> 대요얄ㅇ 데이터에서 특정 값의 위치를 찾을 때 유리
• 정렬된 리스트나 트리에서만 사용할 수 있음

코드를 입력하세요