제로베이스 데이터사이언스 스쿨 - Part 05. 자료구조&알고리즘 with Python -23

Chapter 03. 알고리즘

선형 검색과 이진 검색

1. 주요 개념 요약

이번 글에서는 선형 검색(Linear Search)과 이진 검색(Binary Search)이라는 대표적인 탐색 알고리즘 두 가지를 함께 정리한다. 두 알고리즘은 "데이터 안에서 원하는 값을 어떻게 찾을 것인가"라는 동일한 문제를 다루지만, 전제 조건과 성능 면에서 큰 차이를 가진다.

선형 검색은 데이터가 정렬되어 있지 않아도 사용할 수 있으며, 앞에서부터 하나씩 값을 비교하면서 탐색을 진행한다. 구현이 단순하고 직관적이지만, 데이터의 크기가 커질수록 탐색 시간이 선형적으로 증가한다.

반면 이진 검색은 데이터가 반드시 정렬되어 있어야 한다는 조건을 전제로 한다. 탐색 범위의 가운데 값을 기준으로 좌·우를 절반씩 제거해 나가며 탐색하기 때문에, 탐색 속도가 매우 빠르다. 데이터가 많을수록 선형 검색과의 성능 차이가 뚜렷해진다.

정리하면, 데이터의 상태(정렬 여부)와 크기에 따라 어떤 검색 방법을 선택할지가 결정된다고 볼 수 있다.

---

2. 코드 예시

2-1. 선형 검색 예제

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9]
search_data = 7

search_result_idx = -1

for i in range(len(nums)):
    if nums[i] == search_data:
        search_result_idx = i
        break

print(search_result_idx)

선형 검색은 리스트의 처음부터 끝까지 순서대로 값을 비교한다. 찾는 값이 앞에 있을 경우 빠르게 종료되지만, 맨 뒤에 있거나 없는 경우에는 모든 데이터를 확인해야 한다.

---

2-2. 이진 검색 예제

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums.sort()  # 이진 검색의 핵심 전제: 정렬

search_data = 7
search_result_idx = -1

start_idx = 0
end_idx = len(nums) - 1

while start_idx <= end_idx:
    mid_idx = (start_idx + end_idx) // 2
    mid_val = nums[mid_idx]

    if search_data == mid_val:
        search_result_idx = mid_idx
        break
    elif search_data > mid_val:
        start_idx = mid_idx + 1
    else:
        end_idx = mid_idx - 1

print(search_result_idx)

이진 검색에서는 가운데 인덱스(mid)를 기준으로 탐색 범위를 절반씩 줄여 나간다. 정렬 과정이 필요하지만, 탐색 자체의 효율은 매우 뛰어나다.

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

이번 학습을 통해 단순히 코드를 따라 치는 것보다, 알고리즘이 동작하는 "사고 흐름"을 이해하는 것이 훨씬 중요하다는 점을 느꼈다. 선형 검색은 직관적이어서 처음 접할 때 부담이 없었지만, 연습문제를 통해 데이터가 많아질수록 불필요한 비교가 얼마나 많이 발생하는지 체감할 수 있었다.

이진 검색 실습에서는 특히 정렬의 중요성이 강하게 와닿았다. 정렬이 되어 있지 않으면 이진 검색 자체가 성립하지 않으며, 한 번의 정렬 이후에는 탐색 효율이 극적으로 개선된다는 점이 인상적이었다. 또한 가운데 값을 기준으로 범위를 줄여 나가는 과정에서, 조건 분기 하나가 전체 흐름에 얼마나 큰 영향을 주는지도 직접 확인할 수 있었다.

연습문제를 풀면서 인덱스 범위(start, end)를 잘못 설정하면 무한 루프에 빠질 수 있다는 점도 배웠다. 이 과정에서 알고리즘은 단순한 공식 암기가 아니라, 논리적인 경계 조건을 얼마나 정확히 다루느냐의 문제라는 생각이 들었다.

---

🚀 적용점

• 데이터가 정렬되어 있지 않거나 크기가 작을 경우에는 선형 검색이 구현과 유지 측면에서 유리하다.
• 데이터가 크고 탐색이 자주 발생하는 경우에는 정렬 비용을 감수하더라도 이진 검색이 훨씬 효율적이다.
• 실제 서비스나 프로그램에서는 탐색 알고리즘 선택이 성능에 직접적인 영향을 준다는 점을 고려해야 한다.
• 연습문제를 통해 인덱스 범위, 종료 조건, 정렬 여부를 항상 함께 점검하는 습관이 필요하다고 느꼈다.

이번 정리는 이후 정렬 알고리즘이나 고급 탐색 구조(트리, 해시 등)를 이해하기 위한 중요한 기초가 될 것 같다.