[Python] 이진 탐색

이진 탐색

정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 반드시 오름차순으로 정렬된 상태에서 시작해야 한다.
시간 복잡도는 O(logN)이며 반복문과 재귀 두 방법으로 구현할 수 있다.

1. 배열의 중간 값을 가져온다.
2. 중간 값과 검색 값을 비교한다.
   2-1. 중간 값이 검색 값과 같으면 종료 (mid = key)
   2-2. 중간 값이 검색 값보다 크다면 중간 값 기준 오른쪽 구간을 대상으로 탐색 (mid < key)
   2-3. 중간 값이 검색 값보다 작으면 중간 값 기준 왼쪽 구간을 대상으로 탐색 (mid > key)

💡 특징
일반 탐색은 처음부터 탐색하기 때문에 시간복잡도가 O(n)이지만, 이진 탐색은 계속 반(N/2) 씩 줄여 나가는 알고리즘이기 때문에 O(logN)이다.

# 반복문으로 구현
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)

출처
https://code-angie.tistory.com/3
https://eunsun-zizone-zzang.tistory.com/41