[Python] 이진 탐색

선형탐색은 O(n)의 시간 복잡도

이진탐색은 O(log n)의 시간 복잡도

입력 데이터의 크기가 큰 경우 이진탐색을 떠올려야 함

 

리스트에서 특정 숫자가 몇 번 나왔는지 확인

from bisect import bisect_left, bisect_right

start, end = map(int, input().split())
array = list(map(int, input().split()))

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
# bisect_right(list, num) : list에 num을 넣을 가장 오른쪽 인덱스 반환
def count_by_range(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    print(left_value ,' 의 첫번째 인덱스 : ', left_index)
    right_index = bisect_right(array, right_value)
    print(right_value,' 의 마지막 인덱스 : ', right_index-1)
    return right_index - left_index

count = count_by_range(array, end, end)
if count == 0:
    print(-1)
else:
    print(count)

---

리스트에서 특정 숫자들(범위)이 몇 번 나왔는지 확인

from bisect import bisect_left, bisect_right

start, end = map(int, input().split())
array = list(map(int, input().split()))

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
# bisect_right(list, num) : list에 num을 넣을 가장 오른쪽 인덱스 반환
def count_by_range(array, left_value, right_value):
    left_index = bisect_left(array, left_value)
    print(left_value ,' 의 첫번째 인덱스 : ', left_index)
    right_index = bisect_right(array, right_value)
    print(right_value,' 의 마지막 인덱스 : ', right_index-1)
    return right_index - left_index

count = count_by_range(array, start, end)
if count == 0:
    print(-1)
else:
    print(count)

---

리스트 내 특정 숫자의 인덱스 찾기

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(찾고자 하는 값) 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

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

찾은 숫자의 첫번째 인덱스 값을 출력함