이분 탐색(Binary Search)

이분 탐색 

개념 

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색
• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능 

과정

1. 데이터를 오름차순으로 정렬
2. 자료의 중간값(mid)가 찾고자 하는 값(target)인지 비교
3. mid 값이 target과 다르다면 대소관계를 비교해 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2, 3번 반복
   1. target이 mid보다 작으면 end를 mid 왼쪽 값으로 바꿈
   2. 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

 

시간 복잡도

• O(logN)