[이코테] chapter07 이진 탐색

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

이진 탐색

: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

(1) 순차 탐색

순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

시간 복잡도는 O(N)이다.

 

(2) 이진 탐색: 반으로 쪼개면서 탐색하기

이진 탐색은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는 방법이다.

그래서 내부의 데이터가 이미 정렬디되어 있어야만 사용할수 있는 알고리즘이다.

시간 복잡도는 O(logN)이다.

이진 탐색을 구현하는 방법에는 재귀함수를 사용하는 방법과 반복문을 사용하는 방법이 있다.

1️⃣ 재귀함수로 구현

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 = list(map(int, input))
array = list(map(int, input().split()))

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

2️⃣ 반복문으로 구현

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 NotImplemented

n, target = list(map(int, input))
array = list(map(int, input().split()))

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

(3) 트리 자료구조

(4) 이진 탐색 트리

조건

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다