내일배움캠프 51일차 - 자료구조 & 알고리즘 9주차 : 이진 탐색(녹화본 생성 후 수정)

순차 탐색 - "처음부터 하나씩"

정렬되지 않은 배열에서 값을 찾으려면 veoctor에서 하나씩 순회하면서 비교해간다.

시간 복잡도 O(n)...

※ "정렬된 사전에서 한 글자를 찾을 때, 첫 페이지부터 한 장씩 넘기...

이진 탐색 - "가운데를 보고 절반을 버린다"

정렬된 배열의 가운데(mid)를 보고, 찾는 값이 mid보다 크면 오른쪽 절반만, 작으면 왼쪽 절반만...

왜 O(log n)인가?

매 비교마다 탐색 범위가 절반으로 줄어든다.

n을 계속 2로 나누는 횟수 → log2n

주의사항

배열이 정렬되어 있어야 한다.

 : 정렬되지 않은 데이터에 이진 탐색을 적용하면...

이진탐색 = 분할정복 + 재귀

이진탐색은 분할 정복의 한종류

분할 vs 정복

병합 정렬과의 차이

 : 병합 정렬은 양쪽 모두를 처리, 이진 탐색은 한쪽만 처리한다. O(n log n) vs O(log n)

콜 스택 - 재귀 깊이는 log n

STL의 도구

upper_bound / lower_bound

lower_bound vs upper_bound

활용 패턴

정확한 값 찾기 -

값의 개수 - 

이진탐색의 함정

함정1 - 정렬되지 않은 배열

사진

이진 탐색은 "왼쪽은 작고 오른쪽은 크다"는 정렬 가정 위에서 동작. 그 가정이 깨지면 알고리즘 자체가 무너진다.

함정2 - 정수 오버플로우

함정3 - Off-by-one 에러

left, right의 경게를 잘못 설정하면 무한 루프에 빠진다.

위험한 패턴 vs 안전한 패턴

CS 돋보기

도서관의 카드 목록

도서관에 책 100만 권이 있다고 한다. "제목이 '해리포터'"인 책을 찾아보자.

비교 차이

※ 이것이 바로 데이터베이스...

 B-Tree - 이진 탐색의 진화

실제 노트DB에 이진 트리가 아닌 B-Tree를 사용, 한 노드에 여러 key를 저장하고, 여러 갈래ㅗ 분기.

※ 왜 이진트리가 아니아 B-Tree인가?

하드디스크에서 데이터를 읽을 때 "한번에 많이 읽는 것"이 효율적

정렬의 비용 vs 검색의 이익

표

실전에서는?

게임 개발

게임에서 이진 탐색은 애니메이션 키프레임 보간에 사용된다.

캐릭터 애니메이션의 키프레임이 시간순으로 정렬되어 있을 때, 현재 시간에 해당하는 두 키프레임을 ,./.

 웹/서버

검색 엔진의 핵심이 이진탐색이다.

ㅍ효ㅗㅓ혀ㅑ

CS 저ㅓㄴ반

이진 탐색의 원리 "매번 절반을 버린다"는 정보 이론과 연결된다.

Yes/No 질문 1회로 얻는 정보량 = 1비트

n개 중...

오늘의 핵심

이진 탐색 = "매번 절반을 버리는 것"

 : 정렬된 데이터의 가운데를 보고 한쪽을 통째로 제외 → 한 번에 범위가 반으로

O(log n)의 위력

 : n =100만에서 순차 100만번 vs 이진 20번 - 5만배 차이

이진 탐색 = 분할 정복 + 재귀

7회차 ...