이진 탐색 알고리즘은 배열 내부에서 특정한 값을 찾아내는 알고리즘입니다.
이진 탐색 알고리즘의 과정부터 설명하겠습니다.
1) 배열의 중간에 있는 값을 선택하여 찾고자 하는 값 x와 비교
2) x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로,
3) x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색
4) 값을 찾을 때까지 2번 3번 반복
즉 , 이진 탐색 알고리즘은 정렬되어있는 배열에서 사용해야합니다.( 크기로 비교하기 때문이죠)
예시를 들어볼게요
1 2 4 6 9 10 11 19
이러한 배열이 있다고 했을 때, 4라는 값을 찾는 과정입니다.
1) 먼저 이 배열의 중간값은 6입니다. 배열의 끝점의 인덱스가 7이므로 그의 중간은 3.5에서 소수점을 버리기 때문이죠.
2) 4<6이므로 중간값을 기준으로 왼쪽을 탐색합니다.
3) 저희는 이제 1 2 4 만 탐색하면 됩니다.
4) 1 2 4 의 중간값인 2를 탐색하고 4와 비교합니다.
5) 2<4 이므로 중간값을 기준으로 오른쪽을 탐색합니다.
이제는 코드로 보겠습니다.
fun binarySearch(arr: IntArray, target: Int): Int {
var low = 0
var high = arr.lastIndex
var mid = 0;
while (low <= high) {
mid = (low + high) / 2
when {
arr[mid] == target -> return mid
arr[mid] > target -> high = mid - 1
else -> low = mid + 1
}
}
return -1
}
반응형
'알고리즘' 카테고리의 다른 글
[ 알고리즘 ] 시간 복잡도 구하는 법 (0) | 2020.12.10 |
---|---|
[ 알고리즘 / Kotlin ] 위상 정렬 알고리즘 (0) | 2020.10.20 |
[ 알고리즘 / Kotlin] 플로이드 와샬(Floyd Warshall) 알고리즘 (0) | 2020.10.19 |
[ 알고리즘 / Kotlin ] 백준 17144 미세먼지 안녕! (0) | 2020.10.15 |
[ 알고리즘 / Kotlin ] 백준 3190 뱀 (0) | 2020.10.07 |