Python - 이진 탐색 구현, 라이브러리

- 이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

리스트 안의 특정 데이터를 찾기 위해 처음부터 데이터를 하나씩 확인하는 순차 탐색보다
효율적으로 데이터를 탐색할 수 있다.
즉, 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)이다.

 

• 만약 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18] 라는 리스트가 있다면 시작점은 [0], 끝점은 [9], 중간점은 [4] 다.

짝수개가 들어있는 리스트에서는 소수점 이하를 제거하여 중간값을 구하기 때문에 [5]가 아닌 [4]가 된다.

 

1) 숫자 4가 있는지 확인하고 싶다. 그런데 4는 중간점 값인 '8'보다 작으니까

중간점을 포함한 오른쪽 값은 볼 필요가 없다.

 

2) 그래서 우리는 원래 [9]였던 끝점을 4의 중간점의 왼쪽인 [3]으로 옮겨준다.

즉 총 0, 2, 4, 6 에서 4를 탐색하도록 범위가 좁혀진 것이다. 그럼 이때의 중간점은 [1]이 된다.

시작점[0], 중간점[1], 끝점[3]

 

3) 중간점[1]의 값 '2'보다 4가 더 크므로 중간점을 포함한 왼쪽의 값은 볼 필요가 없다.

마찬가지로 시작점을 중간점 오른쪽 위치로 옮겨준다. 

시작점[2], 중간점[2], 끝점[3]

이 때, 중간점 위치인 [2]의 값 4는 우리가 찾고자하는 값이므로 탐색을 끝낸다.

 

 

(1) 재귀함수 구현

def binary_search(array, target, start, end):
    if start > end:
    	return None
    mid = (start + end) // 2    # 중간점은 시작점과 끝점을 더해서 2로 나눈 몫
    if array[mid] == target:
    	return mid
    elif array[mid] > target:
    	return binary_search(array, target, start, mid-1) # 중간점보다 작으면 중간점을 -1
    else:
    	return binary_search(array, target, mid+1, end) # 중간점보다 크면 중간점을 +1
       
n, target = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1) # 시작점은 0, 끝점은 n-1
if result == None:
	print('원소가 존재하지 않습니다.')
else:
	print(result + 1)

매개변수 array는 리스트, target은 찾고자하는 값을 받아온다.

---

 

(2) 반복문 구현

def binary_search(array, target, stard, end):
    while start <= end:
    	mid = (start + end) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
    return None
    
 # 입력, 출력 코드는 동일

 

---

- 이진 탐색 라이브러리

• bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
• bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스 반환

만약 배열 a = [1, 2, 2, 3, 4]에서 bisect_left(a, 3)을 한다면 3은 2보다 크므로 삽입 가능한 인덱스 [3]이 반환된다.

즉,  [1, 2, 2, 3, 3, 4]가 된다고 생각 했을 때의 인덱스를 구해주는 것이다.

 

이 라이브러리를 사용하여 값이 특정 범위에 속하는 데이터 개수를 구할 수 있다.

from bisect import bisect_left, bisect_right

def count_by_range(a, leftValue, rightValue):
    rightIndex = bisect_right(a, rightValue)
    leftIndex = bisect_left(a, leftValue)
    return rightIndex - leftIndex
    
 a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
 print(count_by_range(a, 4, 4)) # 값이 4인 데이터 개수 출력
 print(count_by_range(a, -1, 3)) # 값이 [-1, 3] 범위에 있는 데이터 개수 출력

 

 

참고 강의: https://youtu.be/94RC-DsGMLo