이진 탐색(Binary Search) 알고리즘
이진 탐색 알고리즘은 이분 탐색 알고리즘이라고도 불리며 검색 범위를 반씩 줄여서 탐색하는 알고리즘입니다.
이진 탐색 알고리즘은 정렬된 리스트에서만 실행할 수 있습니다.
이진 탐색 알고리즘 과정
위와 같은 배열이 있을 때,
x가 존재한다면 배열을 오름차순 했을 때 위치한Index 번호를, 없다면-1을 리턴하세요.
위와 같은 문제가 있다면 배열을 처음부터 하나씩 확인할 수도 있지만 이진 탐색 알고리즘을 사용하여 확인할 수 있습니다.
이진 탐색 알고리즘을 사용하여 해결하는 과정은 다음과 같습니다.
1. 배열을 오름차순으로 정렬합니다. (내림차순이어도 상관은 없지만, 범위 지정 방법이 달라지므로 오름차순으로 정렬하는 것이 기본입니다.)
2. 시작과 끝을 배열의 시작 인덱스와 끝 인덱스로 지정합니다.
3. 시작과 끝의 중간 인덱스를 구합니다.
(시작 인덱스 + 끝 인덱스) / 2가중간 인덱스이 됩니다.
4. 중간 인덱스에 위치한 값이 목표 값과 어떤 관계인지 확인합니다.
- 만약 중간 인덱스에 위치한 값이 목표 값이라면 중간 값을 리턴합니다.
- 만약 중간 인덱스에 위치한 값이 목표 값보다 작다면
시작 인덱스를중간 인덱스 + 1로 변경합니다. - 만약 중간 인덱스에 위치한 값이 목표 값보다 크다면
끝 인덱스를중간 인덱스 - 1로 변경합니다. - 만일, 시작 인덱스와 끝 인덱스가 같다면
-1을 리턴합니다. 아니면 3번 과정으로 돌아갑니다.
이진 탐색 알고리즘 예시1
위의 배열에서
10을 찾아보겠습니다.
1. 배열을 오름차순으로 정렬합니다.
2. 시작 인덱스를 0, 끝 인덱스를 5로 지정합니다.
3-1. (0 + 5) / 2를 하여 중간 인덱스 2를 구합니다.
4-1. index 2에 위치한 6이 10보다 작으므로 시작 인덱스를 2 + 1인 3으로 변경합니다.
3-2. (3 + 5) / 2를 하여 중간 인덱스 4를 구합니다.
4-2. index 4에 위치한 10을 찾았으므로 4를 리턴합니다.
이진 탐색 알고리즘 예시2
위의 과정을 통해
11을 찾아보겠습니다.
1. 배열을 오름차순으로 정렬합니다.
2. 시작 인덱스를 0, 끝 인덱스를 5로 지정합니다.
3-1. (0 + 5) / 2를 하여 중간 인덱스 2를 구합니다.
4-1. index 2에 위치한 6이 10보다 작으므로 시작 인덱스를 2 + 1인 index 3으로 변경합니다.
3-2. (3 + 5) / 2를 하여 중간 인덱스 4를 구합니다.
4-2. index 4에 위치한 10이 11보다 작으므로 시작 인덱스를 4 + 1인 5로 변경합니다.
3-3. (5 + 5) / 2를 하여 중간 인덱스 5를 구합니다.
4-3. index 5에 위치한 12가 11보다 크지만, 시작 인덱스와 끝 인덱스가 같기 때문에 3번 과정으로 돌아가지 않고 -1을 리턴합니다.
이진 탐색 코틀린 코드 예시
위의 예시를 코틀린 코드를 통해 구현하면 다음과 같습니다.
fun binarySearch(arr: IntArray, x: Int): Int {
// 1. 배열을 오름차순으로 정렬 합니다.
arr.sort()
// 2. 시작 인덱스와 끝 인덱스를 지정합니다.
var start = 0
var end = arr.lastIndex
// 3번 과정과 4번 과정을 반복하도록 while문을 사용합니다.
while (start <= end) {
// 3. 중간 인덱스을 구합니다.
val mid = (start + end) / 2
// 4. 중간 인덱스에 위치한 값이 목표 값과 어떤 관계인지 확인합니다.
when {
// 만약 중간 인덱스에 위치한 값이 x라면 중간 인덱스를 리턴합니다.
arr[mid] == x -> return mid
// 만약 중간 인덱스에 위치한 값이 x보다 작다면 시작 인덱스를 "중간 인덱스 + 1"로 바꿉니다.
arr[mid] < x -> start = mid + 1
// 만약 중간 인덱스에 위치한 값이 x보다 크다면 끝 인덱스를 "중간 인덱스 - 1"로 바꿉니다.
arr[mid] > x -> end = mid - 1
}
}
// 배열에서 x를 찾지 못했으므로 -1을 리턴합니다.
return -1
}여기서 while문 부분을 조금 더 설명하면, while문의 조건을 start <= end로 지정한 이유는 시작 인덱스와 끝 인덱스가 같은 경우를 마지막으로 더 이상 3번 과정으로 돌아가 반복하지 않도록 구현한 것입니다.
while문을 반복하는 동안 x를 찾지 못하는 경우에는 start의 값이 계속 증가하거나 end의 값이 계속 감소하게 됩니다.
즉, x가 배열에 존재하지 않는 경우, 결국에는 start와 end가 같은 값을 가지게 됩니다.
이렇게 start와 end가 같은 값을 가지게 되는 경우,
그 위치에 있는 값이 x보다 큰 경우에는 end의 값이 start(end) - 1이 되어 start가 end보다 커지게 되어 while문에서 나오게 됩니다.
그 위치에 있는 값이 x보다 작은 경우에도 start의 값이 start(end) + 1이 되어 start가 end보다 커지게 되어 while문에서 나오게 됩니다.
때문에 while문에서 나오게 되는 경우는 배열에 x가 존재하지 않는 경우가 되고 -1을 리턴하게 되는 것입니다.
이진 탐색 알고리즘 사용시 주의사항
이진 탐색은 배열이 정렬되어 있는 경우에만 사용할 수 있습니다.
이진 탐색을 활용하여 문제를 풀 때 주의할 점 혹은 자신의 알고리즘이 맞는것 같은데 오답이라 뜨는 경우 확인해봐야 할 부분은 아래와 같습니다.
1. while문의 조건이 start <= end가 되어야 하는지, start < end가 되어야 하는지 제대로 파악해야 합니다.
- while문의 조건이 달라지면 처리해야하는 과정이 달라지기 때문에, 자신이 선택한 풀이 과정이 어떤 것인지 정확히 파악해야 합니다.
2. start와 end의 값이 제대로 변하는지 확인해야 합니다.
start가mid + 1로 변해야 하는지mid로 변해야 하는지를 잘 파악해야 합니다.end가mid - 1로 변해야 하는지mid로 변해야 하는지를 잘 파악해야 합니다.
3. 정답이 mid인지 start인지 end인지를 잘 파악해야 합니다.
- 문제에 따라 정답이
mid가 될 수도start가 될 수도,end가 될 수도 있기 때문에 어떤게 정답인지 정확하게 파악할 수 있어야 합니다.
