Binary Search 이분탐색
Binary search
이분탐색
이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾아내는 방법이다.
탐색의 유명한 예로 사전을 들 수가 있다. 사전의 경우, 색인이 있어서 가나다 순이라던가, 주제별로 묶여있어서 우리가 원하는 것을 색인을 통해 찾기도 한다. 하지만 이러한 색인이 없다면, 무지성으로 처음부터 끝까지 한장씩 찾아보는 수 밖에 없다.
만약 정렬되어있는 데이터에서 빠르게 찾는 방법으로 이분탐색이 쓰인다.
문제를 푸는 핵심은 정렬 후, 우리가 원하는 값이 현재 기준(mid)보다 큰지 작은지를 확인하여, 탐색범위를 점차적으로 줄이는 원리를 이해하는 것이다.
실생활에서 이러한 이분 탐색이 쓰이는 경우는 UP and DOWN과 관련이 있다.
A가 자신의 기말 프로그래밍 점수를 맞춰보라고 한다. 0~100점까지 있다고 했을 때 친구 B는 이 0~100까지 수 중 하나를 불러서 맞춰야 한다. 너무 불평등한 조건이기 때문에 업 다운으로 알려준다고 했을 때 과정은 다음과 같다.
B : 50점 이상?
A : ㅇㅇ
B : 70점 이상?
A : ㄴㄴ
여기까지 진행하면 A의 점수는 50~69점으로 추정할 수 있다. 이때 질문을 적게하는 방식은 해당 범위의 반에 해당하는 것을 기준으로 이상인지 이하인지, 그 값인지 확인하는 방식이다.
따라서 범위 left, right에서 그 중간값인 mid(left+right/2)를 통해 mid가 우리가 찾는 값이면 그대로 출력, mid보다 작으면 right의 범위를 mid-1로 mid보다 크면 left를 mid+1로 범위를 설정해서 다시 탐색하는 방식이다.
위와 같이 -3~20까지 정렬된 길이 11인 배열 D가 있다고 보자. 우리가 4라는 값이 어디있는지 찾으려면 이진 탐색을 이용해 다음과 같은 과정을 가진다.
left = 0 , right =10, mid = 5
5번의 값은 9로 4는 9보다 작기 때문에 0~4번 범위로 다시 탐색해야한다. 따라서 범위의 right를 mid-1 = 5로 지정해서 다시 탐색한다.
left = 0 , right = 4, mid = 2
2번의 값은 1로 4는 1보다 크기 때문에 3~4번 범위로 다시 탐색해야한다. 따라서 범위의 left를 mid+1 = 3으로 지정해서 다시 탐색한다.
left = 3 , right = 4, mid =3.5 → 4로 올림(사용자 지정 올림, 내림, 반올림)
4번의 값은 7로 4는 7보다 작기 때문에 3~3번 범위로 다시 탐색해야한다. 따라서 범위의 right를 mid-1 = 3로 지정해서 다시 탐색한다.
left = 3 , right = 3, mid = 3
3번의 값은 4로 우리가 찾는 값이다!
이처럼 처음부터 끝까지 우리가 찾는 값인지 확인하면 10번 연산이 필요하지만, 이진 탐색을 이용하면 약 4번만에 우리가 원하는 것을 찾을 수 있다.
JAVA
...
//x는 우리가 찾는 값
//d[]는 값이 들어간 배열
while(l<=r){
int mid = (l+r)/2;
if(x == d[mid]) {
System.out.println(mid);
break;
}
else if(x>d[mid]) {
l = mid+1;
}
else {
r = mid-1;
}
}
추천문제
Leave a comment