어디 숨었니? 반으로 쪼개며 찾자! - 이진 탐색(Binary Search) 쉽게 배우기

안녕하세요 logro 입니다 :)
오늘은 많은 알고리즘 문제에서 자주 등장하는 이진 탐색(Binary Search)을 쉽게 배워볼 거예요!
"탐색"이라고 하면 뭔가 어렵고 무거운 느낌이 들 수 있지만, 실제로는 "정렬된 목록에서 빠르게 찾는 방법" 정도로 이해하면 OK! 👌

---

🧠 이진 탐색이란?

이진 탐색은 정렬된 데이터에서 원하는 값을 찾을 때 사용하는 알고리즘이에요.
핵심 아이디어는 간단해요:

"가운데 값을 확인하고, 내가 찾는 값이 더 작으면 왼쪽에서, 더 크면 오른쪽에서 다시 찾자!"

 

무작정 처음부터 끝까지 찾는 **선형 탐색(linear search)**보다 훨씬 빠르답니다! 😎

---

🎯 언제 써야 할까?

• 데이터가 정렬되어 있을 때만!
• 빠르게 값을 찾고 싶을 때
• 예: 정렬된 숫자 리스트, 사전 순 정렬된 문자열 등

---

🔍 이진 탐색 흐름 이해하기

비유를 하나 들어볼게요!
당신이 100페이지짜리 책에서 "42페이지"를 찾고 있다고 해요.

1. 처음엔 중간인 50페이지를 펼쳐봐요.
2. "오, 42보다 크네? 그럼 왼쪽(1~49쪽)에 있을 거야!"
3. 다시 그 구간의 중간인 25페이지를 봐요.
4. "이번엔 작네? 그럼 오른쪽(26~49쪽)을 보자!"
5. 이 과정을 반복하면 금방 42페이지를 찾을 수 있어요 🧐

---

🧪 코드로 확인해볼까요?

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # 가운데 인덱스
        if arr[mid] == target:
            return mid  # 찾았다!
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽으로 이동
        else:
            right = mid - 1  # 왼쪽으로 이동

    return -1  # 못 찾았을 때

🧑‍💻 예시:

numbers = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(numbers, 7))  # 출력: 3

7은 인덱스 3에 있으니 맞죠? 🎉

---

⏱️ 시간 복잡도는?

탐색 방법	시간 복잡도
선형 탐색	O(n)
이진 탐색	O(log n)

즉, 1,000,000개의 데이터가 있어도 20번 이하의 비교만으로 찾을 수 있어요! 😲

 

알고리즘의 속도를 말해주는 마법의 도구, 시간 복잡도란?

알고리즘의 속도를 말해주는 마법의 도구, 시간 복잡도란?

---

🧩 정리!

• 이진 탐색은 정렬된 리스트에서만 가능
• 가운데를 기준으로 탐색 범위를 반씩 줄이기
• 시간 복잡도는 O(log n), 매우 효율적!
• 면접, 코딩 테스트 단골 개념 🎯

---

📝 이진 탐색은 다양한 알고리즘의 기반이 되는 아주 중요한 개념이에요.
처음에는 헷갈릴 수 있지만, 직접 구현해보면 금방 익숙해질 거예요.