[Python] 이진 탐색 알고리즘

---

💡 이진 탐색 알고리즘

순차 탐색 : 앞에서부터 하나씩 확인.

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위 절반씩 좁혀가면서 탐색. 시작점, 끝점, 중간점 이용.

 

✔️예시 [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]에서 4 찾기

 

1. 시작점[0], 끝점[9], 중간점[4] (소수점 이하 제거)

0	2	4	6	8	10	12	14	16	18
[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

중간점 기준으로 왼쪽을 탐색할지, 오른쪽을 탐색할지 고르기 : 찾는 값 4가 8보다 작기 때문에 왼쪽으로

 

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

0	2	4	6
[0]	[1]	[2]	[3]

찾는 값 4가 중간값 2보다 크기 때문에 오른쪽으로

 

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

		4	6
		[2]	[3]

 

-> 시간복잡도 O(logN)

 

💡 파이썬 코드 : 재귀적 구현

중간값과 비교하여 시작 인덱스 또는 끝 인덱스를 바꿔 재귀적으로 구현

 

✔️ 코드 설명

 

def 이진탐색 함수 (배열, 찾는 값, 시작 인덱스, 끝 인덱스):

    if 시작 인덱스 > 끝 인덱스 : None

    중간 인덱스 = ( 시작 + 끝 ) // 2

    if 중간 값 == 찾는 값 :  중간 인덱스 반환

    elif 찾는 값이 중간 값보다 작으면 : 재귀(시작 ~ 중간-1)

    else : 재귀(중간+1 ~ 끝)

 

입력받기 - 원소 개수(끝 인덱스), 찾을 값, 전체 원소 리스트

 

출력값 = 이진탐색 함수(입력받은 값)

print(몇번째 인덱스인지)

 

✔️ 코드 구현

def binary_search (array, target, start, end):
    if (start > end): return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)
    
n, target = map(int, input().split())
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None: 
    print("찾는 결과가 없습니다.")
else : 
    print("해당 값은 {}번째 위치에 있습니다.".format(result+1))

 

입력	출력
10 7 1 3 5 7 9 11 13	해당 값은 {}번째 위치에 있습니다.
10 7 1 3 5 6 9 11 13	찾는 결과가 없습니다.

 

 

💡 파이썬 코드 : 반복문 구현

while문 사용하여 시작 인덱스가 끝 인덱스보다 작은 경우에 반복 실행

 

✔️ 코드 설명

 

def 이진탐색 함수 (배열, 찾는 값, 시작 인덱스, 끝 인덱스):

    while 시작 인덱스 <= 끝 인덱스:

        중간 인덱스 = (시작 인덱스 + 끝 인덱스) // 2

        if 중간 값 == 찾는 값 : 중간 인덱스 반환

        elif 중간 값 < 찾는 값 : 끝 인덱스 = 중간 인덱스 - 1

        else : 시작 인덱스 = 중간 인덱스 + 1

    못찾으면 None

 

입력받기 - 원소 개수(끝 인덱스), 찾을 값, 전체 원소 리스트

 

출력값 = 이진탐색 함수(입력받은 값)

print(몇번째 인덱스인지)

 

✔️ 코드 구현

def binary_search (array, target, start, 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
    
n, target = map(int, input().split())
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None: 
    print("찾는 결과가 없습니다.")
else : 
    print("해당 값은 {}번째 위치에 있습니다.".format(result+1))

입력	출력
10 7 1 3 5 7 9 11 13	해당 값은 {}번째 위치에 있습니다.
10 7 1 3 5 6 9 11 13	찾는 결과가 없습니다.

 

💡 biscect 라이브러리

bisect_left(배열, 숫자) : 정렬된 순서 유지하면서 배열 a에 x를 삽일할 가장 왼쪽 인덱스

bisect_right(배열, 숫자) : 정렬된 순서 유지하면서 배열 a에 x를 삽일할 가장 오른쪽 인덱스

1	2	4	4	8
[0]	[1]	[2]	[3]	[4]

위의 리스트의 형태를 배열 a라고 할 때, bisect_left(a, 4)는 2, bisect_right(a, 4)는 4

 

✔️ 코드 구현

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x)) #2
print(bisect_right(a, x)) #4

 

💡 값이 특정 범위에 속하는 데이터 개수 구하기

✔️ 코드 설명

 

def 개수 반환 함수 (배열, 범위 처음 수, 범위 마지막 수):

    오른쪽 인덱스 = biscect_right(배열, right_value)

    왼쪽 인덱스 = biscect_left(배열, right_left)

    return 오른쪽 인덱스 - 왼쪽 인덱스

 

배열 선언

print(개수 변환 함수(배열, 범위 처음 수, 범위 마지막 수)

 

✔️ 코드 구현

from bisect import bisect_left, bisect_right

def count_by_range (array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

array = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
print(count_by_range(array, 4, 4)) #2
print(count_by_range(array, -1, 3)) #6