WEEK02 - TIL 이분 탐색(이진 탐색) / 이진 탐색 트리

순차 탐색: 리스트 안에 있는 특정한 데이터 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 [별다른 말이 없다면 기본적으로 이 방법으로 탐색]

이진 탐색: 정렬되어 있는 리스트에서 (만족한다면) 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

-> 탐색 범위를 정해줘야함. 시작점, 끝점, 중간점.

 

ex.

step1

중간점 선정은 중간점index값에서 소수점 이하는 제거다.

우리가 찾는 값이 4일 때, 중간점 보다 왼쪽에 있으므로, 중간점~끝점까지는 볼 필요가 X

따라서 끝점을 중간점보다 한 칸 왼쪽으로 다시 재지정해준다.

 

step2

끝점의 위치 조정으로 인한 중간점 재지정에 들어감.

이번에도 찾고자 한 값이 중간점보다 오른쪽에 있으므로 시작점~중간점은 볼 필요X

따라서 시작점을 중간점보다 한 칸 오른쪽으로 재지정해준다.

 

step3

이제 중간점이 우리가 찾고자 한 4값과 일치하므로 탐색을 멈춘다!

 

- 이진 탐색의 시간 복잡도는 탐색 범위를 2로 나눈 것과 동일, 즉 연산 횟수는 log₂N에 비례

(초기 개수: 32 > 1단계: 16 > 2단계: 8 > 3단계: 4 …)       ∴ 시간복잡도 O(logN)을 보장

 

 파이썬 소스코드 [재귀적 구현]

import sys

input = sys.stdin.readline

def search(array,target,start,end):
    # start>end일 시 탐색하고자 한 범위에 데이터가 X니까 none값 반환
    if start>end:
        return None

    # 중간점 지정
    mid = (start+end)//2

    # 찾은 경우 중간점 index 반환   
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid]>target:
        return search(array,target,start,mid-1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return search(array,target,mid+1,end)

# 원소의 개수와 찾고자 하는 값 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = search(array,target,0,n-1)
if result == None:
    print('원소X')
# 있다면 몇 번째 원소인지 출력
else:
    print(result+1)

[반복문 구현]

import sys

input = sys.stdin.readline

def 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 = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = search(array,target,0,n-1)
if result == None:
    print('원소X')
# 있다면 몇 번째 원소인지 출력
else:
    print(result+1)

 

* 이진 탐색 라이브러리 [파이썬 편]

from bisect import bisect_left,bisect_right

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

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

import sys
from bisect import bisect_left,bisect_right

input = sys.stdin.readline

# 값이 [left, right]인 데이터의 개수를 반환하는 함수
def countRange(a,left,right):
    rightIndex = bisect_right(a,right)
    leftIndex = bisect_left(a,left)
    return rightIndex - leftIndex

a = [1,2,3,3,3,3,4,4,8,9]

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

- 파라메트릭 서치(Parametric Search)

= 최적화 문제를 결정 문제(예 or 아니오)로 바꾸어 해결하는 기법 [ex. 어떤 함수의 값을 가능한 낮추거나, 높이는 문제]

 

---

- 기본 트리 구조

트리는 부모-자식 구조

최상단: 루트 노드

최하단: 단말 노드

트리를 떼어내도: 서브 트리

 

+ basic. 트리 크기가 N이라고 했을 때, 트리의 간선(줄기)의 개수는 N-1임

 

- 이진 탐색 트리

= 가장 간단한 형태 : 이진 탐색이 동작할 수 있게 고안한 자료구조

 

* 이진 탐색 트리의 특징

1. 부모(루트) 노드보다 왼쪽 자식 노드가 작고

2. 부몬 노드보다 오른쪽 자식 노드가 크다

∴ 즉, 왼쪽 < 부모 < 오른쪽 노드 순으로 크다! 이게 성립되면 == '이진 트리'

ex. 37을 찾는 과정

→ 루트부터 방문하고 → 30<37이네? 왼쪽 노드 볼 가치가 없다~ 하면서 부모랑 함께 안 봄! → 오른쪽 노드로 gogo

→ 이때 48이 루트가 되어 왼쪽과 오른쪽 노드를 비교함. → 왼쪽 찾고(37) 탐색 종료~🕊

 

if. 자식 노드가 없을 때까지 찾지 못하면 == 원소가 없는 것

 

 

+++ 이진 탐색 보강

- 구현 준비

• target : 찾고자 하는 값
• data : 오름차순으로 정렬된 list
• start : data 의 처음 값 인덱스
• end : data 의 마지막 값 인덱스
• mid : start, end 의 중간 인덱스

- 구현 개요

• 자료의 중간 값이 (mid) 찾고자 하는 값인지 검사
• 아니라면 대소관계를 비교하여 start, end 값 이동
• 동일 연산 반복 (재귀로 구현 가능)