정렬된 수에서 하나의 수의 위치 찾기(이진 탐색)
💡 학습 목표
1. 문제 정의
2. 해결 방법
3. 연습 문제
4. 풀이
1. 문제 정의
- 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법
- 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐
- 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음
- 수의 예 : [12, 25, 31, 48, 54, 66, 70, 83, 95, 108]
- 83의 위치를 찾아보세요
- 88의 위치를 찾아보세요
2. 해결 방법
- 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐수 있다.
- 한번 비교 할때 마다 1/2씩 범위가 좁혀진다.
3. 연습 문제
public class BinarySearch {
public static void main(String[] args) {
// 정렬되어 있는 데이터 상태
int[] numbers = { 12, 25, 31, 48, 54, 66, 70, 83, 95, 108 };
int target = 83;
// 이진 탐색을 하기 위해 필요한 초기값을 설정 하시오
int left;
int right;
int mid;
int temp;
boolean find = false;
// 코드를 구현
// 결과
// System.out.println("찾는 수는 " + mid + "번째 있습니다.");
// 또는
// System.out.println("찾는 수가 없습니다.");
}
}
4. 풀이
package useful;
public class BinarySearch {
public static void main(String[] args) {
// 정렬되어 있는 데이터 상태
int[] numbers = { 12, 25, 31, 48, 54, 66, 70, 83, 95, 108};
int target = 84;
// 이진 탐색을 하기 위해 필요한 초기값을 설정 하시오
int left;
int right;
int mid;
int temp;
boolean find = false;
// 코드를 구현
left = 0;
right = numbers.length - 1;
while (!find) {
mid = (right + left) / 2;
if (target == numbers[mid]) {
System.out.println("찾는 수는 인덱스 " + mid + "번째에 있습니다.");
find = true;
} else if (target < numbers[mid]) {
right = mid - 1;
} else if (target > numbers[mid]) {
left = mid + 1;
}
if (right < left) {
System.out.println("찾는 수가 없습니다.");
find = true;
}
}
// 결과
// System.out.println("찾는 수는 " + mid + "번째 있습니다.");
// 또는
// System.out.println("찾는 수가 없습니다.");
}
}
핵심 아이디어
- 반으로 가른 후 한번 비교 → 반쪽을 버리고 배열의 범위를 재정의함
- 이때 반으로 가른 인덱스의 값은 비교를 했기때문에 그 인덱스를 기준으로 ±1
- 종료 시점은 배열의 범위가 음수가 될때
- 처음에는 0이 될때도 생각 해보았지만 target 을 찾는 시점이 반복을 시작할 때고 배열의 범위가 좁혀지는 시점은 target을 찾지 못했을 때이기 때문에 다음번 반복에서 타겟을 찾는 행위를 한번 더 해야함
'Java > Java 유용한 클래스' 카테고리의 다른 글
파일 입력 스트림(문자 기반 스트림) - 14 (0) | 2024.05.20 |
---|---|
문자 기반 스트림 - 13 (0) | 2024.05.17 |
파일 Copy (바이트기반 입/출력) - 12 (0) | 2024.05.16 |
파일 출력 스트림(바이트 기반) - 11 (0) | 2024.05.16 |
파일 입력 스트림(바이트 기반) - 10 (0) | 2024.05.14 |