Binary Search란 정렬되어 있는 데이터에서 원하는 값을 찾는 방법이다.
대상 데이터의 중앙값과 찾고자하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는데,
이때 자료는 반드시 정렬된 상태여야 한다.(예를 들면, 오름/내림차순)
정렬방법에 대해 먼저, 대략적으로 얘기해보면,
1. 자료 중앙에 있는 원소를 고름
2. 중앙 원소의 값과 찾고자 하는 값을 비교
3. 찾고자 하는 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 데이터에 대해서 새로 탐색하고,
크다면 자료의 오른쪽 데이터에 대해 새로 탐색한다.
4. 이를 반복한다.
핵심은 탐색의 범위를 반복적으로 반으로 줄이는 것이다.
이제 자세히 알아보자.
오름차순으로 정렬된 배열 arr = {2, 4, 7, 9, 11, 19, 23}이 있고, 이중 7을 검색하려고 한다.
먼저, 배열의 중앙 원소는 9이다.
직관적으로 중앙 원소가 무엇인지 알 수 있긴 하나, 그 값을 찾는 방법을 다시 말하자면,
맨 처음 index = 0, 마지막 index = 배열의 길이 - 1이므로 중앙 원소가 존재하는 index는 (0+ 배열의 길이 - 1) / 2가 된다.
즉, 배열 arr는 배열의 길이가 7이므로 중앙 원소가 존재하는 index는 (7-1) / 2 == 3.
따라서 중앙값은 arr[3]인 9이다.
이제 중앙 원소의 값(9)과 찾고자 하는 값(7)을 비교해보자.
찾고자 하는 값이 중앙값보다 왼쪽에 있으므로, 중앙값의 왼쪽 데이터에 대해 새로 탐색해야 한다.
이제, 맨 처음 index는 0, 맨 마지막 index는 2가 됐다.
이때의 중앙값은 index 1의 위치의 값인 4가 된다.
중앙값(4)와 찾는 값(7) 중에서 찾는 값이 더 크므로,
즉 찾는 값이 중앙값보다 오른쪽에 있으므로, 중앙값의 오른쪽 데이터에 대해 새로 탐색해야 한다.
그런데, 탐색 범위가 인덱스가 2인 값뿐이고, 찾는 값과 중앙값이 일치하므로 탐색을 성공한 것이다.
이제 코드를 작성하여 알아보도록 하자.
위와 같은 순서로,
1. 탐색의 대상이 되는 자료들이 정렬되어 있는 배열 arr[low]부터 arr[high]사이에 들어있다고 하자.
- 배열의 길이가 N이라고 하면, low는 0번 인덱스, high는 N-1번 인덱스이다.
2. 중간값의 인덱스를 mid라고 하자.
- mid == (low+high) / 2이다.
3. 찾는 값(key값)이 arr[mid]보다 큰지, 작은지를 비교한다.
- key < arr[mid]: 찾는 값이 중간값의 왼쪽에 존재하는 경우이므로 high를 mid-1로 만든다.
- key > arr[mid]: 찾는 값이 중간값의 오른쪽에 존재하는 경우이므로 low를 mid+1로 만든다.
- key == arr[mid]: 찾는 값을 찾음. 중간값을 return해주면 됨
4. low > high가 될 때까지 반복하면서 key값을 찾는다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import java.util.Arrays;
public class List_BianrySearch {
static int[] arr = {4,9,11,23,2,19,7};
public static void main(String[] args) {
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.println(binarySearch(7, 0, arr.length - 1));
}
// key - 구하고자 하는 값
// mid - 중간값에 해당하는 인덱스
// low - 0번 인덱스
// high - (배열의 길이 - 1)번 인덱스
static int binarySearch(int key, int low, int high) {
//중간값
int mid;
while(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) {
return mid;
} else if(key < arr[mid]) { //중간값의 왼쪽에 해당
high = mid - 1; //하나를 빼주면 왼쪽에서 가장 큰 값이 되니까
} else { //중간값의 오른쪽에 해당
low = mid + 1; //하나를 더하면 오른쪽에서 가장 작은 값이 되니까
}
}
return -1; //탐색 실패
}
}
|
cs |
< 코드 작성++ >
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
import java.util.Arrays;
import java.util.Scanner;
public class Main {
// 이진 탐색 소스코드 구현(반복문) -- 오름차순으로 정렬되어 있는 상태에서 이진 탐색!
public static int binarySearch(int[] arr, int target, int start, int end) {
/*
* target: 찾고자 하는 값 start: 탐색 범위 내의 시작 인덱스 end: 탐색 범위 내의 끝 인덱스 mid: start와 end의 중간 위치 인덱스
*/
while (start <= end) {
int mid = (start + end) / 2;
// target이 중간점에 위치할 경우 중간점의 인덱스를 반환한다.
if (arr[mid] == target) {
return mid;
}
// 오름차순 정렬상태이므로 target이 중간점보다 왼쪽에 위치한 경우 왼쪽 범위만 확인
// end = mid - 1
else if (arr[mid] > target) {
return binarySearch(arr, target, start, mid - 1);
}
// target이 중간점보다 오른쪽에 위치한 경우 오른쪽 범위만 확인
// start = mid + 1
else {
return binarySearch(arr, target, mid + 1, end);
}
// 못 찾은 경우 -1 반환
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기
int n = sc.nextInt();
int target = sc.nextInt();
// 전체 원소 입력 받기 + 오름차순 정렬하기
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n-1);
if(result == -1) {
System.out.println("찾는 값이 존재하지 않습니다.");
}
else {
System.out.println("찾는 값의 인덱스는 " + result + "입니다." );
}
}
}
|
cs |
