Chapter 13 - 검색 (Searching)

Chapter 13

검색

Searching

Part 1  검색의 개념과 순차 검색 · Search Basics & Sequential Search
Part 2  이진 검색 · Binary Search
Part 3  이진 검색의 응용과 검색 비교 · Applications & Comparison

01

Part 1

검색의 개념과 순차 검색

Search Basics & Sequential Search

검색이란 무엇인지 이해하고, 가장 기본적인 순차 검색 알고리즘을 배웁니다.

생활 속의 검색

Searching in Daily Life

한국어

우리는 매일 검색하고 있다!

일상 속 검색의 예

전화번호부에서 친구 이름 찾기, 도서관에서 책 찾기, 마트에서 원하는 과자 찾기... 이 모든 것이 "검색"입니다!

검색이 중요한 이유

데이터가 적으면 하나씩 찾아도 금방이지만, 데이터가 많아지면 찾는 방법이 매우 중요해집니다.

뒤죽박죽 단어 퍼즐

알파벳 순서가 없으면 단어 찾는 데 오래 걸림

정렬된 단어 퍼즐

알파벳 순서대로라면 빠르고 쉽게 찾을 수 있음

핵심 발견: 데이터가 정렬되어 있으면 검색이 훨씬 빨라집니다! 이것이 11~12장에서 정렬을 먼저 배운 이유입니다.

실생활 비유 — 방에서 리모컨 찾기

방법 1: 방 구석구석을 처음부터 끝까지 하나씩 뒤진다 → 순차 검색

방법 2: "보통 소파 근처에 있으니까" 하고 범위를 좁혀 찾는다 → 이진 검색처럼 범위를 줄이는 방법

방법 3: 리모컨 보관함을 만들어서 항상 같은 곳에 둔다 → 인덱스(색인) 방식

English

We Search Every Day!

Everyday Search Examples

Finding a friend's name in contacts, looking for a book in a library, searching for snacks at a store... These are all "searching"!

Why Searching Matters

With little data, checking one-by-one is fast. But as data grows, the method of searching becomes critical.

Jumbled Word Puzzle

Without alphabetical order, finding words takes a long time

Sorted Word Puzzle

With alphabetical order, you find words quickly and easily

Key Insight: When data is sorted, searching becomes much faster! That's why we learned sorting in Ch.11-12 first.

Real-life Analogy — Finding a Remote

Method 1: Search every corner of the room one by one → Sequential Search

Method 2: "It's usually near the sofa" — narrow down the area → Like Binary Search

Method 3: Use a remote holder so it's always in the same place → Index approach

검색의 개념

What is Searching?

한국어

검색(탐색)이란?

        검색(Search, 탐색)이란 어떤 데이터 집합에서 원하는 값을 찾는 것입니다.
      

검색의 기본 규칙

1

찾고자 하는 데이터(= 검색 키, Search Key)를 정합니다.

2

데이터 집합(배열, 리스트 등)을 탐색합니다.

3

찾으면 → 해당 위치(인덱스)를 반환합니다.

4

못 찾으면 → -1을 반환합니다. (관례)

왜 -1을 반환할까?
배열의 인덱스는 0부터 시작하므로, 0 이상의 숫자는 모두 유효한 위치입니다. 그래서 "찾지 못했다"는 의미로 절대 인덱스가 될 수 없는 -1을 사용합니다.

검색 알고리즘의 3가지 종류

알고리즘	정렬 필요?	속도	난이도
순차 검색	필요 없음	느림 O(n)	매우 쉬움
이진 검색	필요함	빠름 O(log n)	보통
트리 검색	트리 구조	빠름 O(log n)	어려움

English

What is Searching?

Searching means finding a desired value in a collection of data.

Basic Rules of Searching

1

Define the data to find (= Search Key).

2

Traverse the data collection (array, list, etc.).

3

If found → return the position (index).

4

If not found → return -1. (Convention)

Why return -1?
Array indices start at 0, so every non-negative number is a valid position. -1 can never be an index, making it the perfect "not found" signal.

Three Types of Search Algorithms

Algorithm	Sorted?	Speed	Difficulty
Sequential	Not needed	Slow O(n)	Very Easy
Binary	Required	Fast O(log n)	Medium
Tree	Tree structure	Fast O(log n)	Hard

순차 검색이란?

What is Sequential Search?

한국어

순차 검색 (Sequential Search)

        순차 검색은 배열의 처음부터 끝까지 하나씩 차례대로 비교하면서 원하는 데이터를 찾는 방법입니다.
      

비유: 출석부에서 이름 찾기

선생님이 출석부에서 "김철수"를 찾으려면, 1번부터 차례대로 이름을 확인합니다. "아, 15번에 있네!" — 이것이 순차 검색입니다.

순차 검색의 특징

장점

- 이해하기 가장 쉬운 검색 방법

- 데이터가 정렬되어 있지 않아도 사용 가능

- 구현이 매우 간단

단점

- 데이터가 많으면 매우 느림

- 최악의 경우 모든 데이터를 다 확인해야 함

- 데이터 100만 개면 최대 100만 번 비교!

시간 복잡도

경우	비교 횟수	설명
최선 (Best)	1번	첫 번째에서 바로 발견
평균 (Average)	n/2번	중간쯤에서 발견
최악 (Worst)	n번	마지막에 있거나 없음

O(n)이란? 데이터가 n개이면, 최대 n번 비교해야 한다는 뜻입니다. 데이터가 2배가 되면 시간도 2배!

English

Sequential Search

        Sequential Search checks each element from start to end, one by one, comparing until it finds the target.
      

Analogy: Finding a Name in a Roster

A teacher looking for "Kim Cheolsu" checks names starting from #1 in order. "Found at #15!" — this is Sequential Search.

Characteristics

Advantages

- Easiest search method to understand

- Works even on unsorted data

- Very simple to implement

Disadvantages

- Very slow with large data

- Worst case: must check every element

- 1 million items = up to 1 million comparisons!

Time Complexity

Case	Comparisons	Description
Best	1	Found at the first position
Average	n/2	Found around the middle
Worst	n	At the end or not found

What is O(n)? With n items, you may need up to n comparisons. Double the data = double the time!

비정렬 데이터의 순차 검색 — 성공

Sequential Search on Unsorted Data — Success

한국어

정렬되지 않은 배열에서 찾기 (성공)

배열 [188, 150, 168, 162, 105, 120, 177, 50]에서 162를 찾는 과정:

포인트: 찾는 값이 중간에 있어서 4번만 비교하면 됐습니다. 하지만 운이 나쁘면 8번(전체) 비교해야 합니다!

English

Finding in Unsorted Array (Success)

Find 162 in [188, 150, 168, 162, 105, 120, 177, 50]:

Point: The target was in the middle, so only 4 comparisons needed. But in the worst case, all 8 elements must be checked!

비정렬 데이터의 순차 검색 — 실패

Sequential Search on Unsorted Data — Failure

한국어

정렬되지 않은 배열에서 찾기 (실패)

배열 [188, 150, 168, 162, 105, 120, 177, 50]에서 999를 찾는 과정:

비정렬 순차 검색의 문제점: 찾는 값이 없을 때, 모든 데이터를 끝까지 확인해야만 "없다"고 결론 내릴 수 있습니다. 데이터가 100만 개면 100만 번 비교 후에야 "없음"을 알 수 있습니다!

알고리즘 흐름도

English

Finding in Unsorted Array (Failure)

Find 999 in [188, 150, 168, 162, 105, 120, 177, 50]:

Problem with Unsorted Sequential Search: When the value doesn't exist, you must check every single element to conclude "not found." With 1 million items, that's 1 million comparisons just to say "not here"!

Algorithm Flowchart

비정렬 순차 검색 — 파이썬 코드

Unsorted Sequential Search — Python Code

한국어

Code13-01: 비정렬 순차 검색

가장 기본적인 순차 검색 코드입니다. 한 줄씩 이해해 봅시다!

## 함수 선언 부분 ##
def seqSearch(ary, fData) :
    pos = -1              # 못 찾으면 -1
    size = len(ary)       # 배열 크기
    for i in range(size) :
        if ary[i] == fData : # 발견!
            pos = i
            break           # 즉시 종료
    return pos

## 전역 변수 선언 부분 ##
dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = int(input('찾을 값 입력: '))

## 메인 코드 부분 ##
position = seqSearch(dataAry, findData)
if position == -1 :
    print(findData, '없음')
else :
    print(findData, '위치:', position)

코드 한 줄씩 설명

1

pos = -1 → 처음에는 "못 찾음" 상태로 시작

2

for i in range(size) → 0번부터 끝까지 반복

3

if ary[i] == fData → 현재 값이 찾는 값인지 비교

4

break → 찾았으면 더 이상 반복할 필요 없이 즉시 종료!

break가 중요한 이유: break가 없으면 이미 찾았는데도 끝까지 반복합니다. 불필요한 비교를 줄여 효율을 높입니다!

English

Code13-01: Unsorted Sequential Search

The most basic sequential search code. Let's understand it line by line!

## Function Declaration ##
def seqSearch(ary, fData) :
    pos = -1              # -1 if not found
    size = len(ary)       # Array size
    for i in range(size) :
        if ary[i] == fData : # Found!
            pos = i
            break           # Exit immediately
    return pos

## Global Variables ##
dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = int(input('Enter value: '))

## Main Code ##
position = seqSearch(dataAry, findData)
if position == -1 :
    print(findData, 'not found')
else :
    print(findData, 'at position:', position)

Line-by-Line Explanation

1

pos = -1 → Start with "not found" state

2

for i in range(size) → Loop from index 0 to end

3

if ary[i] == fData → Compare current value with target

4

break → Once found, stop immediately!

Why break matters: Without break, the loop continues even after finding the target. break eliminates unnecessary comparisons!

정렬된 데이터의 순차 검색

Sequential Search on Sorted Data

한국어

정렬된 배열에서의 순차 검색 — 개선!

비유: 사전에서 단어 찾기

영어 사전에서 "cat"을 찾다가 "dog"이 나왔다면? 이미 지나쳤으니 더 볼 필요 없습니다! 사전은 정렬되어 있으니까요.

개선 포인트

        데이터가 정렬되어 있으면, 찾는 값보다 큰 값을 만나는 순간 검색을 중단할 수 있습니다. 더 뒤에는 더 큰 값만 있으니까요!
      

정렬된 배열 [50, 105, 120, 150, 162, 168, 177, 188]에서 100을 찾는 과정:

개선된 코드 (Code13-02)

def seqSearch(ary, fData) :
    pos = -1
    for i in range(len(ary)) :
        if ary[i] == fData :
            pos = i
            break
        elif ary[i] > fData :  # 핵심! 더 큰 값이면 중단
            break
    return pos

dataAry.sort()  # 반드시 정렬 먼저!

elif ary[i] > fData : break — 이 두 줄이 핵심입니다! 정렬된 데이터에서 찾는 값보다 큰 값을 만나면 "이 뒤에는 절대 없다"는 것을 알 수 있으므로 바로 중단합니다.

English

Sequential Search on Sorted Array — Improved!

Analogy: Finding a Word in a Dictionary

Looking for "cat" in a dictionary, if you see "dog" — you've passed it! No need to keep looking! The dictionary is sorted.

Key Improvement

        When data is sorted, if you encounter a value larger than the target, you can stop immediately. Everything after is even larger!
      

Find 100 in sorted [50, 105, 120, 150, 162, 168, 177, 188]:

Improved Code (Code13-02)

def seqSearch(ary, fData) :
    pos = -1
    for i in range(len(ary)) :
        if ary[i] == fData :
            pos = i
            break
        elif ary[i] > fData :  # Key! Stop if bigger
            break
    return pos

dataAry.sort()  # Must sort first!

elif ary[i] > fData : break — These two lines are the key! In sorted data, if you find a value larger than the target, you know it can't exist further, so stop immediately.

순차 검색 비교: 비정렬 vs 정렬

Sequential Search: Unsorted vs Sorted

한국어

비정렬 vs 정렬 순차 검색 비교

항목	비정렬 순차 검색	정렬 순차 검색
데이터 정렬	필요 없음	반드시 필요
검색 성공 시	같음	같음
검색 실패 시	끝까지 비교 (느림)	중간에 중단 가능 (빠름)
시간 복잡도	O(n)	O(n) (but 평균 빠름)
코드 추가	기본 코드	elif + sort() 추가

Self13-01: 같은 값 모두 찾기

배열 [188, 50, 150, 168, 50, 162, 105, 120, 177, 50]에서 50이 있는 모든 위치를 리스트로 반환하는 순차 검색 함수를 작성하세요.

힌트: break를 없애고, 결과를 리스트에 append하세요!

def seqSearch(ary, fData) :
    posList = []
    for i in range(len(ary)) :
        if ary[i] == fData :
            posList.append(i)
    return posList

dataAry = [188,50,150,168,50,162,105,120,177,50]
result = seqSearch(dataAry, 50)
print('50의 위치:', result)
# 출력: 50의 위치: [1, 4, 9]

English

Unsorted vs Sorted Sequential Search

Item	Unsorted Sequential	Sorted Sequential
Sorting needed?	No	Yes, required
When found	Same	Same
When not found	Check all (slow)	Stop early (faster)
Time Complexity	O(n)	O(n) (but avg. faster)
Code change	Basic code	Add elif + sort()

Self13-01: Find All Occurrences

In [188, 50, 150, 168, 50, 162, 105, 120, 177, 50], write a sequential search that returns all positions of 50 as a list.

Hint: Remove break, and append results to a list!

def seqSearch(ary, fData) :
    posList = []
    for i in range(len(ary)) :
        if ary[i] == fData :
            posList.append(i)
    return posList

dataAry = [188,50,150,168,50,162,105,120,177,50]
result = seqSearch(dataAry, 50)
print('Position of 50:', result)
# Output: Position of 50: [1, 4, 9]

02

Part 2

이진 검색

Binary Search

데이터를 반씩 잘라내며 빠르게 찾는 이진 검색의 원리와 구현을 학습합니다.

이진 검색이란?

What is Binary Search?

한국어

이진 검색 (Binary Search)

        이진 검색은 정렬된 데이터에서 중간값과 비교하여 절반씩 범위를 줄여나가는 검색 방법입니다.
      

비유: 숫자 맞추기 게임 (업다운 게임)

"1~100 사이의 숫자를 맞춰보세요!"

"50!" → "더 크다!" → "75!" → "더 작다!" → "62!" → "정답!"

매번 범위가 절반으로 줄어듭니다. 이것이 바로 이진 검색의 원리입니다!

이진 검색의 핵심 조건

반드시 데이터가 정렬되어 있어야 합니다!
정렬되지 않은 데이터에는 이진 검색을 사용할 수 없습니다. 중간값을 기준으로 왼쪽/오른쪽을 판단하려면 순서가 있어야 하기 때문입니다.

왜 이진 검색이 빠를까?

비교 횟수가 기적적으로 줄어듦

데이터 수	순차 검색 (최대)	이진 검색 (최대)
10개	10번	4번
1,000개	1,000번	10번
1,000,000개	1,000,000번	20번
10억 개	10억 번	30번

놀라운 사실: 데이터가 10억 개여도 이진 검색은 최대 30번만 비교하면 됩니다! 순차 검색이라면 10억 번 비교해야 하는데 말이죠.

English

Binary Search

        Binary Search works on sorted data by comparing with the middle value and halving the search range each time.
      

Analogy: Number Guessing Game (High-Low)

"Guess a number between 1 and 100!"

"50!" → "Higher!" → "75!" → "Lower!" → "62!" → "Correct!"

The range halves every time. This is exactly how Binary Search works!

Critical Requirement

Data MUST be sorted!
Binary search cannot work on unsorted data. You need order to decide whether to go left or right from the middle.

Why is Binary Search So Fast?

Dramatically Fewer Comparisons

Data Size	Sequential (max)	Binary (max)
10	10	4
1,000	1,000	10
1,000,000	1,000,000	20
1 Billion	1 Billion	30

Amazing fact: Even with 1 billion items, binary search needs only 30 comparisons! Sequential search would need 1 billion.

이진 검색 동작 과정 — 성공

Binary Search Step-by-Step — Success

한국어

이진 검색으로 162 찾기

정렬된 배열 [50, 60, 105, 120, 150, 160, 162, 168, 177, 188]에서 162를 찾아봅시다!

English

Binary Search for 162

Find 162 in sorted [50, 60, 105, 120, 150, 160, 162, 168, 177, 188]:

1

start=0, end=9, mid=4 → ary[4]=150. Since 150 < 162, move start to mid+1=5. (Discard left half)

2

start=5, end=9, mid=7 → ary[7]=168. Since 168 > 162, move end to mid-1=6. (Discard right half)

3

start=5, end=6, mid=5 → ary[5]=160. Since 160 < 162, move start to mid+1=6.

4

start=6, end=6, mid=6 → ary[6]=162. Found! Return index 6

        Only 4 comparisons to find the value in an array of 10 elements! Sequential search might have needed up to 10.
      

The Key Idea: Divide and Conquer

Divide & Conquer (분할 정복)

Binary search repeatedly divides the search range in half and conquers by choosing which half to keep.

Each step eliminates 50% of remaining data — that's why it's so fast!

이진 검색 동작 과정 — 실패

Binary Search — Failure Case

한국어

이진 검색 실패는 언제?

        시작(start)이 끝(end)보다 커지면 검색에 실패한 것입니다. 더 이상 검색할 범위가 없다는 뜻입니다!
      

배열 [50, 60, 105, 120, 150]에서 80을 찾는 과정:

1

start=0, end=4, mid=2 → ary[2]=105. 105 > 80 → end = 1

2

start=0, end=1, mid=0 → ary[0]=50. 50 < 80 → start = 1

3

start=1, end=1, mid=1 → ary[1]=60. 60 < 80 → start = 2

!

start=2 > end=1 → 검색 범위 없음! → -1 반환 (실패)

쉽게 기억하기: start와 end가 서로 엇갈리면(start > end) "더 이상 찾을 곳이 없다"는 뜻입니다. 마치 두 손가락이 교차하면 사이에 아무것도 없는 것과 같습니다!

English

When Does Binary Search Fail?

        When start becomes greater than end, the search has failed. There's no more range to search!
      

Find 80 in [50, 60, 105, 120, 150]:

1

start=0, end=4, mid=2 → ary[2]=105. 105 > 80 → end = 1

2

start=0, end=1, mid=0 → ary[0]=50. 50 < 80 → start = 1

3

start=1, end=1, mid=1 → ary[1]=60. 60 < 80 → start = 2

!

start=2 > end=1 → No range left! → Return -1 (failed)

Easy to remember: When start and end cross each other (start > end), it means "nowhere left to look." Like two fingers crossing — nothing between them!

이진 검색 — 파이썬 코드

Binary Search — Python Code

한국어

Code13-03: 이진 검색 구현

def binSearch(ary, fData) :
    pos = -1
    start = 0                     # 시작 위치
    end = len(ary) - 1            # 끝 위치

    while (start <= end) :         # 범위가 유효한 동안
        mid = (start + end) // 2  # 중앙 계산
        if fData == ary[mid] :     # 찾았다!
            return mid
        elif fData > ary[mid] :    # 오른쪽 절반
            start = mid + 1
        else :                      # 왼쪽 절반
            end = mid - 1

    return pos                     # -1 반환 (실패)

## 사용 예 ##
dataAry = [50,60,105,120,150,160,162,168,177,188]
findData = 162
position = binSearch(dataAry, findData)
if position == -1 :
    print(findData, '없음')
else :
    print(findData, '위치:', position)

코드 핵심 3줄 분석

1

mid = (start + end) // 2
시작과 끝의 중간 인덱스를 계산합니다. //는 나눗셈 후 소수점 버림(정수 나눗셈)입니다.

2

start = mid + 1
찾는 값이 중앙보다 크면, 왼쪽 절반은 필요 없으므로 시작을 중앙 다음으로 이동합니다.

3

end = mid - 1
찾는 값이 중앙보다 작으면, 오른쪽 절반은 필요 없으므로 끝을 중앙 이전으로 이동합니다.

주의! mid + 1과 mid - 1에서 +1, -1을 빠뜨리면 무한 루프에 빠질 수 있습니다!

English

Code13-03: Binary Search Implementation

def binSearch(ary, fData) :
    pos = -1
    start = 0                     # Start position
    end = len(ary) - 1            # End position

    while (start <= end) :         # While range is valid
        mid = (start + end) // 2  # Calculate middle
        if fData == ary[mid] :     # Found!
            return mid
        elif fData > ary[mid] :    # Right half
            start = mid + 1
        else :                      # Left half
            end = mid - 1

    return pos                     # Return -1 (failed)

## Usage Example ##
dataAry = [50,60,105,120,150,160,162,168,177,188]
findData = 162
position = binSearch(dataAry, findData)
if position == -1 :
    print(findData, 'not found')
else :
    print(findData, 'at position:', position)

The 3 Key Lines Explained

1

mid = (start + end) // 2
Calculates the middle index. // is integer division (drops decimal).

2

start = mid + 1
If target > middle value, discard left half by moving start past mid.

3

end = mid - 1
If target < middle value, discard right half by moving end before mid.

Caution! Forgetting the +1 and -1 in mid + 1 and mid - 1 can cause an infinite loop!

이진 검색 — 알고리즘 흐름도

Binary Search — Algorithm Flowchart

한국어

이진 검색 흐름도

English

Binary Search Flowchart

Step-by-step Algorithm

1

Set start = 0, end = len(array) - 1

2

While start <= end:
Calculate mid = (start + end) // 2

3

If target == ary[mid] → Return mid (found!)

4

If target > ary[mid] → start = mid + 1 (go right)

5

If target < ary[mid] → end = mid - 1 (go left)

6

If loop ends without finding → Return -1 (not found)

Time Complexity: O(log n)

What does log n mean?

log₂(n) means "how many times can you divide n by 2?"

log₂(8) = 3 → divide 8 in half 3 times to get 1

log₂(1024) = 10 → divide 1024 in half 10 times

log₂(1,000,000) ≈ 20 → only 20 steps for a million items!

Memory aid: Every time data doubles, binary search needs just one more comparison. That's the power of O(log n)!

Part 2 실습문제

Part 2 Practice Problems

한국어

Self13-02: 이진 검색 비교 횟수 세기

10만 개의 랜덤 데이터를 정렬한 후, 이진 검색으로 특정 값을 찾을 때 비교 횟수를 출력하세요.

힌트: 전역 변수 count를 사용하여 while 루프 안에서 매번 1씩 증가시키세요!

import random

def binSearch(ary, fData) :
    global count
    start = 0
    end = len(ary) - 1
    while (start <= end) :
        count += 1          # 비교 횟수 증가
        mid = (start + end) // 2
        if fData == ary[mid] :
            return mid
        elif fData > ary[mid] :
            start = mid + 1
        else :
            end = mid - 1
    return -1

dataAry = [random.randint(0,100000)
           for _ in range(100000)]
dataAry.sort()
findData = random.randint(0,100000)
count = 0
pos = binSearch(dataAry, findData)
print('비교 횟수:', count, '회')
# 결과: 대부분 17회 이하!

Ex13-01: 순차 vs 이진 성능 비교

100만 개의 랜덤 데이터에서 같은 값을 순차 검색과 이진 검색으로 찾아보고, 각각 몇 번 비교했는지 출력하세요.

힌트: 순차 검색은 비정렬 배열, 이진 검색은 정렬 배열을 사용하세요!

import random
count = 0

def seqSearch(ary, fData) :
    global count
    for i in range(len(ary)) :
        count += 1
        if ary[i] == fData :
            return i
    return -1

def binSearch(ary, fData) :
    global count
    start, end = 0, len(ary)-1
    while start <= end :
        count += 1
        mid = (start+end)//2
        if fData == ary[mid] : return mid
        elif fData > ary[mid] : start = mid+1
        else : end = mid-1
    return -1

dataAry = [random.randint(0,999999)
           for _ in range(1000000)]
dataAry.insert(random.randint(0,1000000), 7878)
sortedAry = sorted(dataAry)

count = 0
seqSearch(dataAry, 7878)
print('순차:', count, '회')

count = 0
binSearch(sortedAry, 7878)
print('이진:', count, '회')
# 결과 예: 순차 50만회 vs 이진 20회!

English

Self13-02: Count Binary Search Comparisons

Sort 100,000 random numbers, then binary search for a value and print the number of comparisons.

Hint: Use a global variable count, increment by 1 each loop iteration!

import random

def binSearch(ary, fData) :
    global count
    start = 0
    end = len(ary) - 1
    while (start <= end) :
        count += 1          # Increment count
        mid = (start + end) // 2
        if fData == ary[mid] :
            return mid
        elif fData > ary[mid] :
            start = mid + 1
        else :
            end = mid - 1
    return -1

dataAry = [random.randint(0,100000)
           for _ in range(100000)]
dataAry.sort()
findData = random.randint(0,100000)
count = 0
pos = binSearch(dataAry, findData)
print('Comparisons:', count)
# Result: Usually 17 or less!

Ex13-01: Sequential vs Binary Performance

With 1 million random items, search for the same value using both sequential and binary search. Print the comparison count for each.

Hint: Use unsorted array for sequential, sorted for binary!

# Sequential: ~500,000 comparisons
# Binary: ~20 comparisons
# That's 25,000x faster!
# (See Korean side for full code)

03

Part 3

이진 검색의 응용과 검색 비교

Applications & Comparison

색인(인덱스)을 활용한 이진 검색 응용과 검색 알고리즘 전체 비교를 학습합니다.

색인(인덱스)이란?

What is an Index?

한국어

색인 (Index)

        색인(인덱스)이란 순서가 없는 데이터에서 특정 항목만 추출하여 정렬한 별도의 표입니다. 원본 데이터의 위치 정보를 함께 저장합니다.
      

비유: 교과서 뒷부분의 '찾아보기'

교과서 뒤에 있는 "찾아보기"(색인)를 생각해보세요. "배열 → 45페이지, 스택 → 120페이지" 같은 것이죠.

책 전체를 뒤지지 않고도 원하는 주제의 페이지를 바로 찾을 수 있습니다!

색인이 필요한 이유

도서관 책장에 책이 꽂혀 있다고 합시다:

['어린왕자', '이방인', '부활', '신곡', '돈키호테', '동물농장', '데미안', '파우스트', '대지']

이 순서로는 빠른 검색이 불가능합니다. 하지만 도서명 색인표를 만들면:

['대지→8', '데미안→6', '돈키호테→4', '동물농장→5', '부활→2', '신곡→3', '어린왕자→0', '이방인→1', '파우스트→7']

정렬된 색인표에서 이진 검색을 할 수 있습니다!

English

Index

        An Index is a separate, sorted table extracted from unsorted data. It stores both the key and the original position.
      

Analogy: Book Index

Think of the "Index" at the back of a textbook. "Array → p.45, Stack → p.120"

You can find the page of any topic instantly without flipping through the whole book!

Why Do We Need an Index?

Imagine books on a shelf:

['Little Prince', 'Stranger', 'Resurrection', 'Inferno', 'Don Quixote', ...]

In this order, fast search is impossible. But with a Title Index:

['Don Quixote→4', 'Inferno→3', 'Little Prince→0', ...]

Now we can use binary search on the sorted index!

How Index Search Works

1

Extract the column you want to search by (e.g., title)

2

Sort the extracted column, keeping original positions

3

Use binary search on the sorted index

4

Use the stored position to access original data

Real-world use: Databases use indexes extensively. When you search for a product by name on a shopping website, it uses an index behind the scenes!

색인 활용 이진 검색 — 코드

Index-based Binary Search — Code

한국어

Code13-04: 도서관 책 찾기

책장 데이터에서 색인을 만들고 이진 검색으로 찾는 예제입니다.

from operator import itemgetter

def makeIndex(ary, pos) :
    beforeAry = []
    index = 0
    for data in ary :
        beforeAry.append( (data[pos], index) )
        index += 1
    sortedAry = sorted(beforeAry,
                       key=itemgetter(0))
    return sortedAry

def bookSearch(ary, fData) :
    start, end = 0, len(ary)-1
    while start <= end :
        mid = (start+end)//2
        if fData == ary[mid][0] :
            return ary[mid][1]  # 원본 위치!
        elif fData > ary[mid][0] :
            start = mid+1
        else :
            end = mid-1
    return -1

bookAry = [['어린왕자','쌩떽쥐베리'],
           ['이방인','까뮈'],
           ['부활','톨스토이'], ...]
nameIndex = makeIndex(bookAry, 0)
authIndex = makeIndex(bookAry, 1)

핵심 이해

1

makeIndex: 원하는 열(도서명 또는 작가)을 추출하고, 원본 위치(index)와 함께 튜플로 저장 후 정렬

2

bookSearch: 이진 검색으로 색인에서 찾고, 찾으면 ary[mid][1]로 원본 위치를 반환

3

같은 데이터, 다른 색인: nameIndex(도서명)와 authIndex(작가명) 두 개의 색인을 만들어 다양한 검색 가능!

English

Code13-04: Library Book Search

Create an index from bookshelf data and use binary search.

from operator import itemgetter

def makeIndex(ary, pos) :
    beforeAry = []
    index = 0
    for data in ary :
        beforeAry.append( (data[pos], index) )
        index += 1
    sortedAry = sorted(beforeAry,
                       key=itemgetter(0))
    return sortedAry

def bookSearch(ary, fData) :
    start, end = 0, len(ary)-1
    while start <= end :
        mid = (start+end)//2
        if fData == ary[mid][0] :
            return ary[mid][1]  # Original pos!
        elif fData > ary[mid][0] :
            start = mid+1
        else :
            end = mid-1
    return -1

Key Understanding

1

makeIndex: Extracts desired column (title or author), stores with original position as tuple, then sorts

2

bookSearch: Binary search on the index, returns ary[mid][1] (the original position)

3

Same data, different indexes: Create nameIndex (by title) and authIndex (by author) for flexible searching!

Key Concept — Tuple: (data[pos], index) creates a tuple. [0] is the search key, [1] is the original position. Tuples are like pairs of information bundled together!

트리 검색 소개

Introduction to Tree Search

한국어

이진 탐색 트리 (Binary Search Tree)

        이진 탐색 트리는 이진 트리(Ch.8)의 특별한 형태로, "왼쪽 자식 < 부모 < 오른쪽 자식" 규칙을 따르는 트리입니다.
      

비유: 20 질문 게임

"동물인가요?" → "예" → "다리가 4개인가요?" → "아니오" → "날 수 있나요?" → "예" → "독수리!"

매번 예/아니오로 범위를 좁혀가는 것이 트리 검색과 비슷합니다!

이진 탐색 트리 규칙

모든 노드에 대해:

- 왼쪽 서브트리의 모든 값 < 현재 노드의 값

- 오른쪽 서브트리의 모든 값 > 현재 노드의 값

트리 검색의 장단점:
장점: 검색이 O(log n)으로 빠름
단점: 삽입/삭제 시 트리 구조 유지가 복잡함. 자세한 구현은 이후 과정에서 학습합니다!

English

Binary Search Tree (BST)

        A Binary Search Tree is a special binary tree (Ch.8) that follows the rule: "left child < parent < right child."
      

Analogy: 20 Questions Game

"Is it an animal?" → "Yes" → "Does it have 4 legs?" → "No" → "Can it fly?" → "Yes" → "Eagle!"

Narrowing down with yes/no at each step is similar to tree search!

BST Rule

For every node:

- All values in the left subtree < current node's value

- All values in the right subtree > current node's value

Searching in a BST: Find 60

1

Start at root: 50. Since 60 > 50 → go right

2

At node 70. Since 60 < 70 → go left

3

At node 60. Found! Only 3 comparisons!

BST Pros & Cons:
Pro: Search is O(log n) — fast!
Con: Maintaining tree structure during insert/delete is complex. Detailed implementation is covered in advanced courses!

검색 알고리즘 전체 비교

Complete Comparison of Search Algorithms

한국어

세 가지 검색 알고리즘 종합 비교

항목	순차 검색	이진 검색	트리 검색
정렬 필요	필요 없음	필수	트리 구조
시간 복잡도	O(n)	O(log n)	O(log n)
구현 난이도	매우 쉬움	쉬움	어려움
데이터 추가/삭제	쉬움	재정렬 필요	복잡
적합한 상황	소량 데이터	대량 정적 데이터	동적 데이터
10만 개 최대 비교	100,000회	17회	17회

어떤 검색을 선택할까?
- 데이터가 적으면 (100개 이하) → 순차 검색으로 충분!
- 데이터가 많고 변하지 않으면 → 이진 검색이 최고!
- 데이터가 자주 추가/삭제되면 → 트리 검색 고려

English

Complete Comparison of Three Search Algorithms

Item	Sequential	Binary	Tree
Sorting	Not needed	Required	Tree structure
Time	O(n)	O(log n)	O(log n)
Difficulty	Very Easy	Easy	Hard
Insert/Delete	Easy	Need re-sort	Complex
Best for	Small data	Large static data	Dynamic data
100K max comp.	100,000	17	17

Decision Guide

Sequential O(n)

Simple but slow. Good for small datasets (<100) or unsorted data.

Binary O(log n)

Fast! Best for large, sorted, rarely changing data.

Tree O(log n)

Good for data that changes frequently (inserts/deletes).

Which search to choose?
- Small data (under 100) → Sequential is enough!
- Large static data → Binary Search is the best!
- Frequently changing data → Consider Tree Search

응용예제: 편의점 판매 물건 세기

Application: Counting Store Sales

한국어

Ex13-02: 편의점 판매 물건 개수 세기

편의점에서 오늘 판매된 물건 목록(중복 포함)에서 각 물건이 몇 개 팔렸는지 세는 프로그램입니다.

import random

def binSearch(ary, fData) :
    start, end = 0, len(ary)-1
    while start <= end :
        mid = (start+end)//2
        if fData == ary[mid] : return mid
        elif fData > ary[mid] : start=mid+1
        else : end=mid-1
    return -1

dataAry = ['바나나맛우유', '레쓰비',
  '츄파춥스', '도시락', '삼다수',
  '코카콜라', '삼각김밥']
sellAry = [random.choice(dataAry)
           for _ in range(20)]
sellAry.sort()

sellProduct = list(set(sellAry))
countList = []
for product in sellProduct :
    count = 0
    pos = 0
    while pos != -1 :
        pos = binSearch(sellAry, product)
        if pos != -1 :
            count += 1
            del(sellAry[pos])
    countList.append((product, count))
print("결산:", countList)

코드 동작 설명

1

random.choice로 판매 목록 20개를 랜덤 생성

2

set()으로 중복 제거 → 판매된 물건 종류 파악

3

각 물건을 이진 검색으로 찾고, 찾을 때마다 del로 제거하며 카운트

English

Ex13-02: Counting Store Sales

Count how many of each item was sold today from a sales list (with duplicates).

How the Code Works

1

random.choice generates 20 random sales records

2

set() removes duplicates → get unique product list

3

Binary search for each product, del when found, count occurrences

Example Output

Today's sales (20 items):

['삼각김밥', '코카콜라', '바나나맛우유', '삼다수', '삼다수', '코카콜라', ...]

Results:

[('바나나맛우유', 3), ('삼각김밥', 4), ('삼다수', 5), ('코카콜라', 2), ...]

Alternative approach: In Python, you could also use collections.Counter for this task! But this example demonstrates how binary search can be applied to real-world counting problems.

Important Concepts Used

New Python Features

random.choice(list) — randomly picks one item from a list

set(list) — removes all duplicates from a list

del(list[index]) — removes an item at a specific index

13장 종합 정리

Chapter 13 Summary

한국어

이번 장에서 배운 것

Part 1: 검색의 개념과 순차 검색

- 검색은 데이터 집합에서 원하는 값을 찾는 것

- 순차 검색: 처음부터 끝까지 하나씩 비교 → O(n)

- 정렬된 데이터에서는 더 일찍 중단 가능

- 못 찾으면 -1을 반환 (관례)

Part 2: 이진 검색

- 정렬된 데이터에서 중간값과 비교하여 절반씩 줄여가며 검색 → O(log n)

- 10억 개 데이터도 최대 30번 비교로 검색 가능!

- start, end, mid 세 변수를 사용

- start > end가 되면 검색 실패

Part 3: 색인과 검색 비교

- 색인(Index): 비정렬 데이터에 정렬된 검색표를 만듦

- 이진 탐색 트리: 왼쪽 < 부모 < 오른쪽 규칙

- 상황에 따라 적합한 검색 알고리즘 선택이 중요!

English

What We Learned

Part 1: Search Basics & Sequential Search

- Searching = finding a desired value in a data collection

- Sequential: compare one by one from start → O(n)

- Sorted data allows earlier termination

- Returns -1 when not found (convention)

Part 2: Binary Search

- Compare with middle, halve range each time → O(log n)

- 1 billion items needs at most 30 comparisons!

- Uses three variables: start, end, mid

- Fails when start > end

Part 3: Index & Comparison

- Index: create a sorted lookup table for unsorted data

- BST: left < parent < right rule

- Choosing the right algorithm for the situation matters!

        Key Takeaway: Sorting enables faster searching. The combination of sorting + binary search is one of the most fundamental and powerful techniques in computer science!
      

Part 3 실습문제

Part 3 Practice Problems

한국어

종합 실습 1: 학생 성적 검색 시스템

학생 데이터 [['홍길동',85], ['김영희',92], ['박철수',78], ['이미나',95], ['최강',88]]에서 이름으로 검색하여 성적을 출력하는 프로그램을 작성하세요.

조건: 색인(인덱스)을 만들어 이진 검색을 사용하세요!

from operator import itemgetter

def makeIndex(ary, col) :
    temp = []
    for i in range(len(ary)) :
        temp.append((ary[i][col], i))
    return sorted(temp, key=itemgetter(0))

def binSearch(idx, name) :
    s, e = 0, len(idx)-1
    while s <= e :
        m = (s+e)//2
        if name == idx[m][0] :
            return idx[m][1]
        elif name > idx[m][0] :
            s = m+1
        else :
            e = m-1
    return -1

students = [['홍길동',85],['김영희',92],
  ['박철수',78],['이미나',95],
  ['최강',88]]
nameIdx = makeIndex(students, 0)

name = '박철수'
pos = binSearch(nameIdx, name)
if pos != -1 :
    print(name,'성적:',students[pos][1])
else :
    print(name, '없음')

종합 실습 2: 알고리즘 선택 문제

다음 상황에 가장 적합한 검색 알고리즘은?

① 전화번호부(500만 건)에서 이름으로 검색
② 친구 5명의 생일 목록에서 특정 날짜 검색
③ 쇼핑몰에서 상품이 계속 추가/삭제되는 목록 검색

            ① 이진 검색 — 전화번호부는 이름순 정렬, 대용량 → O(log n)

            ② 순차 검색 — 5명이면 어떤 알고리즘이든 빠름, 단순한게 최고

            ③ 트리 검색 — 데이터가 자주 변경 → 매번 재정렬 부담 없는 트리 적합

English

Comprehensive 1: Student Grade Lookup

Given [['Hong',85], ['Kim',92], ['Park',78], ['Lee',95], ['Choi',88]], write a program that searches by name and prints the grade.

Requirement: Use an index with binary search!

# Same approach as Korean side:
# 1. makeIndex extracts names + positions
# 2. Sort the index alphabetically
# 3. binSearch finds the name in index
# 4. Use returned position to get grade
# from original array

Comprehensive 2: Algorithm Selection

Which search algorithm is best for each scenario?

① Search by name in a phone book (5 million entries)
② Search for a date in a list of 5 friends' birthdays
③ Search a shopping mall product list that keeps changing

            ① Binary Search — phone book is sorted by name, large dataset → O(log n)

            ② Sequential Search — only 5 entries, any algorithm is fast, simplest wins

            ③ Tree Search — frequent insertions/deletions → tree avoids re-sorting overhead