📌 이진 탐색이란?
이진 탐색(Binary Search)은 정렬된 데이터에서 원하는 값을 효율적으로 탐색하는 알고리즘! 🎯
기능 | 특징 | 시간 복잡도 |
타깃 데이터 탐색 | 중앙값 비교를 통한 대상 축소 방식 | O(logN) |
🔍 이진 탐색의 주요 특징
- 빠른 탐색
- 이진 탐색은 정렬된 데이터에서 탐색을 수행하므로 **O(log N)**의 시간 복잡도를 가진다.
- 데이터 크기가 커질수록 선형 탐색보다 훨씬 효율적이다.
- 정렬 필수
- 이진 탐색을 사용하기 위해선 데이터가 반드시 정렬되어 있어야 한다.
- 정렬이 되어 있지 않다면, 먼저 정렬한 후 탐색해야 한다.
🔧 이진 탐색의 활용과 문제 유형
- 활용 사례
- 🔢 숫자 데이터 탐색
- 📚 사전처럼 정렬된 텍스트 탐색
- 🛒 가격 또는 범위를 기준으로 정렬된 상품 탐색
- 문제 유형
- ✅ 특정 값의 존재 여부 확인
- ✅ 특정 조건을 만족하는 값의 최대/최소 찾기
- ✅ Lower Bound / Upper Bound 문제
🚫 이진 탐색 사용 시 주의할 점
- 정렬 여부 확인
- 탐색 전 데이터가 정렬되어 있는지 반드시 확인해야 해요!
- 정렬이 안 되어 있다면 오름차순 정렬을 먼저 수행해야 해요.
- 무한 루프 방지
- 탐색 범위를 좁히지 못하면 무한 루프에 빠질 수 있어요.
- 매번 left, right 값을 적절히 업데이트해야 해요.
- 정확한 종료 조건 설정
- while (left <= right)와 같은 종료 조건이 중요해요.
- 종료 조건이 없으면 탐색이 끝나지 않아요!
🥐 이진 탐색 과정
⭐️ 오름차순 정렬 기준
1️⃣ 중앙값 선택
- 현재 탐색 범위의 중앙값을 선택
- 중앙값 = (left + right) / 2
2️⃣ 타깃과 비교
- 중앙값이 타깃 값보다 큰지 작은지 비교
- 중앙값 > 타깃 값: 왼쪽 범위를 탐색.
- 중앙값 < 타깃 값: 오른쪽 범위를 탐색.
3️⃣ 범위 업데이트
- 왼쪽 또는 오른쪽 범위를 갱신:
- 왼쪽 탐색: right = mid - 1.
- 오른쪽 탐색: left = mid + 1
4️⃣ 탐색 종료
- 중앙값 == 타깃 값: 탐색 성공! 🎉
- left > right: 탐색 실패.
⭐️ 내림차순 정렬 기준
1️⃣ 중앙값 선택
- 현재 탐색 범위의 중앙값을 선택
- 중앙값 = (left + right) / 2
2️⃣ 타깃과 비교
- 중앙값이 타깃 값보다 큰지 작은지 비교
- 중앙값 < 타깃 값: 왼쪽 범위를 탐색.
- 중앙값 > 타깃 값: 오른쪽 범위를 탐색.
3️⃣ 범위 업데이트
- 왼쪽 또는 오른쪽 범위를 갱신:
- 왼쪽 탐색: right = mid - 1
- 오른쪽 탐색: left = mid + 1
4️⃣ 탐색 종료
- 중앙값 == 타깃 값: 탐색 성공! 🎉
- left > right: 탐색 실패.
🔍 정리
- 오름차순 정렬: 타깃 값이 중앙값보다 작으면 왼쪽, 크면 오른쪽!
- 내림차순 정렬: 타깃 값이 중앙값보다 크면 왼쪽, 작으면 오른쪽!
💡 이진 탐색 동작 방식 예제
✅ 데이터셋
3, 7, 13, 15, 23, 35, 38, 41, 46, 49, 55, 67, 68, 72, 77, 86
1️⃣ 초기 설정
- 탐색 범위: left = 0, right = 15 (배열 인덱스 기준).
- 중앙값 계산: mid = (left + right) / 2 = (0 + 15) / 2 = 7.
- 중앙값 데이터: 41.
🔎 비교:
- 41 < 55.
- 결론: 55는 41보다 크므로, 오른쪽 범위를 탐색.
- 새로운 탐색 범위: left = 8, right = 15.
2️⃣ 두 번째 탐색
- 탐색 범위: left = 8, right = 15.
- 중앙값 계산: mid = (8 + 15) / 2 = 11.
- 중앙값 데이터: 67.
🔎 비교:
- 67 > 55.
- 결론: 55는 67보다 작으므로, 왼쪽 범위를 탐색.
- 새로운 탐색 범위: left = 8, right = 10.
3️⃣ 세 번째 탐색
- 탐색 범위: left = 8, right = 10.
- 중앙값 계산: mid = (8 + 10) / 2 = 9.
- 중앙값 데이터: 49.
🔎 비교:
- 49 < 55.
- 결론: 55는 49보다 크므로, 오른쪽 범위를 탐색.
- 새로운 탐색 범위: left = 10, right = 10.
4️⃣ 네 번째 탐색
- 탐색 범위: left = 10, right = 10.
- 중앙값 계산: mid = (10 + 10) / 2 = 10.
- 중앙값 데이터: 55.
🔎 비교:
- 55 == 55.
- 결론: 탐색 성공! 🎉
- 55의 위치: 인덱스 10.
💡 결론
- 최대 연산 횟수: log₂(16) = 4.
- 실제 탐색 연산: 4번 만에 완료!
- 전제 조건: 데이터는 오름차순 정렬되어 있어야 함.
✅ 다음 게시글에서 예제 문제로 더 자세히 이해해보도록 하겠습니다!
[JAVA][Baekjoon] 1300번 K번째 수 🌟🌟🌟🌟🌟
https://www.acmicpc.net/problem/1300 📌 접근 방식처음엔 이걸 이진 탐색으로 풀 생각조차 하지 못했다.. 전혀 이 문제를 보고 이진 탐색을 떠올릴 수 없었다...배열 B의 크기가 매우 커지기 때문에 이 배
nyeroni.tistory.com
[JAVA][Baekjoon] 1920번 수 찾기
https://www.acmicpc.net/problem/1920📌 접근 방식1️⃣ 이진 탐색 사용배열 A를 정렬하여 이진 탐색의 전제 조건(정렬된 배열)을 충족.M개의 수를 각각 A에 대해 이진 탐색을 사용해 존재 여부를 확인.이
nyeroni.tistory.com
[JAVA][Baekjoon] 2343번 기타 레슨 🌟
https://www.acmicpc.net/problem/2343📌 접근 방식이 문제는 주어진 강의들을 최소한의 블루레이 크기로 M개의 블루레이에 나누어 담는 문제이다.중요한 점은 블루레이에 담는 강의의 순서가 바뀌면 안
nyeroni.tistory.com

'CS > 알고리즘' 카테고리의 다른 글
[알고리즘] 정수론 : 소수(Prime number) 구하기 (0) | 2025.01.09 |
---|---|
[알고리즘] 그리디 알고리즘(Greedy Algorithm) (1) | 2025.01.07 |
[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search) (0) | 2025.01.06 |
[알고리즘] 깊이 우선 탐색 : DFS(Depth-First-Search) (0) | 2025.01.04 |
[알고리즘] 기수 정렬(Radix Sort)이란? (0) | 2025.01.03 |