이분탐색 - [알고리즘] [kotlin]

이분탐색이란?

배열에서 특정 원소를 찾는 방법 중 하나.

정렬된 배열에만 적용할 수 있다.

즉, string, number 등 비교 가능한 타입에 적용할 수 있다.

// 자체적으로 비교할 수 없거나 사전순, 크기순이 아닌 방식으로 비교하는 방법은 최하단에 다룬다.

 

동작

0.

- start: 찾는 범위의 시작 index

- end: 찾는 범위의 끝 index

- mid: 범위의 가운데 index

 

1. 정렬된 배열의 찾는값과 mid에 있는 값을 비교한다.

 

2. 목표값이 mid에 있는 값보다 크다면 비교범위를 (mid +1) ~ (end)로 바꾼다.

// 작다면 start ~ (mid - 1)

 

3. 찾는값이 mid에 있는 값과 같으면 mid를 반환하여 index를 알린다.

 

4. 만약 start가 end보다 커진다면 더이상 비교할 범위가 없으므로 찾는값이 없다고 판단한다.

 

 

- 만약 mid가 찾는값보다 작다면 더 큰 값들이 있는 위쪽 Index에는 목표값이 없음을 알 수 있다.

- 만약 mid가 찾는값보다 크다면 더 작은 값들이 있는 아래쪽 index에는 목표값이 없음을 알 수 있다.

즉, 찾아야 하는 범위는 매번 1/2로 줄어든다.

때문에, logN의 시간 복잡도를 갖는다.

 

 

Comparator?

사전순, 크기순이 아닌 방식으로 정렬 및 비교하거나, Comparable을 상속받지 않아 비교할 수 없는 객체를 이분탐색 하고싶을 수 있다.

 

이때는 comparator로 비교 기준을 정의하고, sort 및 binarySearch에 같은 기준을 적용하면 된다.

 

 

// 또는 Comparable을 상속받는 class를 만들어 compareTo 함수를 구현해 사용할 수도 있다.