728x90
반응형
1. 지금까지 학습한 부분 정리 (자료구조)
- 스택 : 프링글스 통 (마지막에 넣은 게 먼저 나옴)
- 큐 : 놀이공원 줄 (먼저 온 사람이 먼저 나옴)
- 덱 : 양쪽이 뚫린 터널 (양방향 큐)
스택과 큐가 도구였다면, 이분 탐색은 그 도구를 효율적으로 다루는 지능이라고 할 수 있다.
2. 업-다운(Up-Down) 게임의 필승법
이분 탐색(Binary Search)은 술자리 게임인 업-다운 게임과 완벽하게 똑같다.
상황 : 1부터 100까지 숫자 중, 술래가 생각한 숫자(70)를 맞춰야한다.
- 하수 (순차 탐색, O(N)) : 1 -> 2 -> 3 ...
- 고수 (이분 탐색, O(log N)) : 중간을 찌름 (질문 한 번에 후보가 절반씩 소거된다.)
3. 조건 : 반드시 숫자가 순서대로 정렬이 되어야 한다.
이분 탐색 코드를 짤 때는 항상 정렬이 되어야 그 뒤에 절반씩 자를 수 있다.
4. 코드 구현
// 이미 정렬된 배열(arr)에서 target 찾기
public static int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2; // 정확히 중간 지점
if (arr[mid] == target) {
return 1; // 찾았다!
} else if (arr[mid] < target) {
start = mid + 1; // Up! (왼쪽 절반 버림)
} else {
end = mid - 1; // Down! (오른쪽 절반 버림)
}
}
return 0; // 끝까지 없으면 실패
}728x90
반응형
'Coding Test' 카테고리의 다른 글
| 코딩 테스트 명심해야할 사항 (0) | 2026.01.29 |
|---|---|
| 자료구조 - 원형 큐(Circular Queue) (0) | 2026.01.29 |
| 자료구조 - 큐(Queue) (0) | 2026.01.29 |
| 자료구조 - 스택(Stack) (0) | 2026.01.29 |
| 자료구조 - 배열(Array) vs 연결 리스트(Linked List) (0) | 2026.01.29 |