[Python]이분탐색/이진탐색

이진탐색이란?

오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 원하는 숫자(target)을 찾는 알고리즘이다. (정렬된 배열에서 빠르게 원하는 원소를 찾는 방법)

이진탐색 알고리즘

1. 시간복잡도: O(logN)
2. 방법
   1) 배열을 오름차순으로 정렬
   2) 배열의 중간값(middle)이 찾고자 하는 값(target)인지 탐색
   3) middle 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고,
   target = middle이 될 때 까지 탐색범위 변경
   • target 값이 middle 보다 작으면 end를 middle 왼쪽 값으로 변경
   • target 값이 middle 보다 크면 start를 middle 오른쪽 값으로 변경

이진탐색 코드

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

이진탐색 라이브러리

from bisect import bisect_left, bisect_right
a = [1,1,3,4,5,6,7]
b = [1,2,3,4,5,6,7]
c = 2
print(bisect_left(a, c),bisect_right(a, c))
>>> 2 2
print(bisect_left(b, c),bisect_right(b, c))
>>> 1 2

1. 배열 안에 해당 값 없으면 해당 값을 넣었을 때의 인덱스 값
2. 배열 안에 해당 값 있으면 해당 값의 왼쪽 인덱스, 오른쪽 인덱스 값 (bisect_left, bisect_right)