✨ Binary Search란?
Binary Search, 이진탐색, 이분탐색 이라고 불리는 탐색 알고리즘의 종류이며,
순차적탐색을 이용했을 때, 성능이 나오지 않을 경우 사용할 수 있습니다.
이진/이분 이라는 뜻처럼 mid값을 중심으로 왼쪽/오른쪽 어디에 값이 있는지를 판단하며,
탐색범위를 1/2로 줄여나가며 찾는 방법입니다.
쉽게 예를 들면,
up&down 게임과 같은 논리인데요,
1~100 중에 내가 생각한 숫자를 맞혀봐! 했을 때 1부터 100까지 하나씩 부르는 것보다
50 -> down, 25 -> up 이런식으로 찾는게 더 빠르다는 방식입니다.
하지만 이 방식이 무조건적으로 빠르다기보다는 모수가 많을 때, 더 효율적이겠죠?
구현 방식에는 크게 2가지로
- 특정값이 있는지만을 찾는 방식이 있고,
- upper bound, lower bound를 통해 범위를 찾는 방법이 있습니다.
Binary Search를 쓰기 위해서는 무조건 정렬이 되어있어야 합니다!!!
예시를 들어보는게 빠른 이해에 도움이 될테니 바로 예시로 들어가겠습니다.
💡 배열 속 값 찾기
arr라는 int배열에 1 3 5 7 9 11 이라는 숫자가 들어가 있다고 가정해보겠습니다.
위에 첫 loop에서는 Start포인트 = 0, End포인트 - 5,
Mid=(0+5)/2=2.5지만 int형이므로 2가 저장이 됩니다.
이렇게 찾은 Mid는 Index를 의미하는 것으로
실질적인 값이 들어있는 arr[Mid]와 찾을 값을 비교해봅니다.
arr[2] = 5이므로 7보다 작으니 mid로부터 오른편에 있는 것이 되겠죠?
그러니 start를 mid+1을 해줍니다. start=mid가 아닌 +1을 해주는 이유는,
이미 arr[mid] 와 7을 비교했을 때 값이 다르다는 것을 알았으니 mid에서 +나 -를 해줘야합니다.
2번째 loop입니다.
start는 아까 1번째 mid에서 +1을 한 값으로 3이 저장됐고, end는 그대로입니다.
arr[mid]가 가리키는 값이 9이므로, 타겟인 7보다 작죠?
이제는 end포인트를 움직여야 합니다. 아까는 오른편으로 이동을 했으니 +를 했지만,
이번에는 왼편으로 이동해야 하므로 mid에서 -1을 해줍니다.
mid가 3이 됐습니다. arr[mid] 가 가리키는 값이 7로 우리가 찾는 값과 동일하네요.
값을 찾는 것만이 목표라면 true를 해당 값의 index를 찾는게 목표라면 mid값을 return하면 되겠습니다.
이 문제와 같은 방식의 백준 문제를 풀어본 적이 있는데 여기를 참고해주시면 도움이 될 것 같네요.
아래는 간단한 예시입니다!
입력값 예시 =
1 2 4 7 5 9
2
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader inputStr = new BufferedReader(new InputStreamReader(System.in));
// 스페이스를 간격으로 배열을 입력해주시면 됩니다.
String[] numList = inputStr.readLine().split(" "); // 입력값 문자배열
float[] cardList = new float[numList.length]; // 숫자로 저장할 배열
// 찾을 값을 입력해주시면 됩니다.
Float tmp = Float.parseFloat(inputStr.readLine()); // 찾을 값
StringBuilder out = new StringBuilder(); // 결과 출력 변수
// Input의 길이만큼 반복하여 float형으로 파싱
for(int i = 0; i < numList.length; i++) {
cardList[i] = Float.parseFloat(numList[i]);
}
// 값을 순차적으로 정렬
Arrays.sort(cardList);
// 출력값 = binary결과
out.append(binary(cardList, tmp));
System.out.println(out);
}
public static int binary(float[] arr, float a) {
int start = 0; // 시작점
int end = arr.length - 1; // 종료점
int mid; // 중간값
// while문은 end가 start보다 커지면 값이 없는 것
while(start <= end) {
mid = (start+end)/2;
if(a < arr[mid]) {
// 찾을 값이 중간값보다 작거나 같을 경우
end = mid - 1;
}else if(a > arr[mid]){
// 찾을 값이 중간값보다 클 경우
start = mid + 1;
}else {
return mid;
}
}
return 0;
}
}💡 배열 속 값의 범위 찾기
위의 binary Search와 같은 방식으로 하되,
우리가 찾는 7이라는 값이 시작하는 점(=하한점, lower bound)과 끝나는 점(=상한점, upper bound)을 찾아 2와 3을 return하게 됩니다.
자세한 부분은 아래 소스를 보는게 더 이해가 쉬울 것 같습니다.
구현 방식이 다르니 참고해주시면 도움 많이 될 것 같아요~
이 문제와 같은 방식의 백준 문제는 여기를 참고해주세요~
아래는 범위로 찾는 방식의 예시를 간단하게 짜보았습니다.
입력값예시 =
1 3 3 3 5 5 7 7 7 7 7 9 15
7
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader inputStr = new BufferedReader(new InputStreamReader(System.in));
// 스페이스를 간격으로 배열을 입력해주시면 됩니다.
String[] numList = inputStr.readLine().split(" "); // 입력값 문자배열
float[] cardList = new float[numList.length]; // 숫자로 저장할 배열
// 찾을 값을 입력해주시면 됩니다.
Float tmp = Float.parseFloat(inputStr.readLine()); // 찾을 값
StringBuilder out = new StringBuilder(); // 결과 출력 변수
// Input의 길이만큼 반복하여 float형으로 파싱
for(int i = 0; i < numList.length; i++) {
cardList[i] = Float.parseFloat(numList[i]);
}
// 값을 순차적으로 정렬
Arrays.sort(cardList);
// 출력값 = 상한점 - 하한점
out.append((upper(cardList, tmp) - lowwer(cardList, tmp)));
System.out.println(out);
}
public static int lowwer(float[] arr, float a) {
int start = 0; // 시작점
int end = arr.length; // 종료점
int mid; // 중간값
// while문은 start지점과 end지점이 같아지면 종료
while(start < end) {
mid = (start+end)/2;
if(a <= arr[mid]) {
// 찾을 값이 중간값보다 작거나 같을 경우
end = mid;
}else {
// 찾을 값이 중간값보다 클 경우
start = mid + 1;
}
}
return start;
}
public static int upper(float[] arr, float a) {
int start = 0;
int end = arr.length;
int mid;
while(start < end) {
mid = (start+end)/2;
if(a < arr[mid]) {
// lower와 같은 방식이지만, 상한점을 찾는 것이므로 찾을 값과 같을 경우에도 start를 움직인다.
end = mid;
}else {
start = mid + 1;
}
}
return start;
}
}