Untitled

Fold the Video

26강 이진 탐색 개요

하나씩 확인하는 방법

다시말해

별다른 말이 없다면 기본적으로

정렬되어 있는

절반씩 좁혀가며 데이터를

정리

순차탐색(단순히 그냥 데이터를 하나하나씩 확인하는 것) 리스트에서 특정 데이터가 존재하는지를 검사할때 별다른 말이 없으면 기본적으로 순차탐색임

데이터를 탐색할수 있다는 저에서 log 시간의 시간복잡도를

정리

이진 탐색은 기본적으로 리스트가 정렬되어 있을때 사용이 가능 하며 이러한 조건을 만족한다고 하면 탐색 범위를 빠르게 절반씩 좁혀 나가면서 데이터를 탐색할수 있다는 점에서 log 시간의 시간복잡도를 가질수 있음

이진탐색은 탐색 범위를 정해줘야함 이때 탐색 범위를 명시하기 위해 시작점 끝점을 명시(인덱스를 의미함)하고 그 시작점에 중간지점을 중간점이라고 표현함

이러한 세가지 변수를 이용해서 탐색범위를 절반씩 좁혀 나가면서 이진 탐색을 수행 할수 있습니다

중간점이라고 표현

절반씩 좁혀나가면서

탐색하고 싶기 때문에

정리

중간점을 봣을때 값이 8임 그럼 중간점 포함 이후에 값은 볼필요가 없은 4보다 커서

그래서 끝점을 중간점 바로 왼쪽으로 옮겨서

다시 중간점을 찾음 값은 2임

중간점을 포함한 왼쪽 값을 볼필요가 없음 4보다 작아서

시작점을 중간점 우측으로 옮김

시작점 중간점 동시에 가리키는게 4임 찾고자 하는 데이터를 찾았음

** 시작점 중간점 동시에 가리키는 것이 본질이 아님 이럴 경우가 있을수 있지만

** 중간점이 가리키는게 맞아야 정답을 도출했다고 할수 있음

# 이진 탐색 소스코드 구현 (재귀 함수)
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(찾고자 하는 값)을 입력 받기
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)

현재 코드는 재귀 함수를 이용해서 작성한 코드임

def binary_search(array, target, start, end):

이와같이 탐색을 수행하고자 하는 배열 정보가 들어오고 그리고 찾고자 하는 데이터 탐색 범위가 주어지게 됨 일단 가장먼저 소스를 보면

스타트가 엔드보다 크다면 탐색하고자 하는 범위의 데이터가 동일하므로 이와같이

데이터가 존재하지 않는다고 none 값을 반환 할수 있도록 함

시작점에다가 끝점을 더한 값에서 이를 나눈 몫을 중간점이라고 명시할수 있습니다

하구요

인덱스 라고 할수 있습니다

중간점의 값보다 찾고자 하는 값이 작은 경우에는 중간점 위치를 포함해

큰 값들이 존재

리턴 할수

찾고자 하는 값이

그래서 이와 같이 작성된 이진 탐색함수를 이용해서 실제로 이진탐색을 수행 해볼수 있는데요

찾고자

이진 탐색을 수행한 결과를

none

있는데요

이 반복 구문이 수행 될때마다 현재 중간점 위치에 값을 확인해서 찾고자 하는 데이터를 찾았는지를 검사할수 있고

만약 찾지 못했다면 마찬가지로 탐색범위를 좁혀 가는 방법을 사용할 수 있습니다

정리

이진탐색 구현은 반복문을 통해서도 가능함

값에 인덱스를 리턴

위해서 이 끝점을 중간점 보다 1 작은 값으로 갱신 할수 있도록 합니다

마찬가지 로직으로 중간점에 값보다 찾고자 하는 값이 더 큰 경우에는 오른쪽 부분을 탐색할 필요가 있기 때문에 시작점에 값을 중감점에 1을 더한 값으로 갱신 할수 있도록 합니다

데이터 예시를 넣어서 이진탐색을 수행한 결과를 확인해 보시면 아까 확인했던 결과와 동일하게 출력되는것을 확인할수 있습니다

바이너리 서치 함수

확인해 보시면 하나의 어뤠이 정보를 입력받을때 포인터를 사용하거나 이와같이 백터 라이브러리를 사용하되 별도로 변수를

그 벡터 변수에

만약 &(엔퍼센드)를 빼주게 되면 이 함수를 호출할때 기존 백터에 담겨있던

값을 카피 하기 때문에 시간 복잡도가 O(N)이 됩니다 그렇기 때문에

설정한 뒤에

찾고 자 하는 값과 동일할때 해당 인덱스를 반환 할수 있도록 하는

부분을 탐색할수 있도록 하고 마찬가지로 중간점에 값보다 찾고자 하는 값이 큰경우에는

원소가 존재하지

바이너리 서치 함수

매 스텝 마다

수 있도록 하고

반씩 줄이면서

걸 확인할수 있습니다

바이섹트 레프트 , 라이트

참고로 파이썬에서 바이섹트 레프트는 C++에서의 로얼 바운드와 동일하며

바이섹트 라이트는 c++의 어펄 바운드와 사실상 같다고 볼수 있습니다

바이섹트 레프트 하는 역할은

배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 하는 거고요

바이섹트 롸이트는 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환하는 함수라고 할수 있습니다

바이섹트 레프트 4라는 원소에 대해서 이진 탐색을 수행하면 이 4라는 원소가 들어갈

첫번째 위치인 인덱스 2가 반환이 되구요

그림에서

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 배열 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range (a, -1, 3))

#실행 결과
#2
#6