cr00   2년 전

https://kotlinlang.org/api/lat...

java/kotlin의 내장 binarySearch는 찾고자 하는 값이 여러 개 있을 때 그 중 어떤 원소의 인덱스를 반환할지 순서가 보장되지 않습니다.

그래서 정확한 범위를 구하려면 발견된 인덱스에서 시작해서 왼쪽, 오른쪽으로 언제까지 해당 값이 나타나는지 계산해야 하는데..

당연히 한 칸씩 탐색하면 O(n)이니 안 되고, LCA 찾듯이 2의 배수씩 탐색하면 O(log n)으로 되기야 하겠지만..

이거 구현할 노력으로 그냥 직접 upper bound, lower bound 구현하는 게 더 나을 거 같아서.. 어떻게 할까 생각해봤는데

정수 배열을 실수 배열로 바꾸고, 찾고자 하는 값에 0.5를 뺀 값을 해당 실수 배열에서 binarySearch로 찾으면 됩니다.

0.5를 빼는 이유는, 찾고자 하는 값과 (찾고자 하는 값 - 1)의 사잇값을 구하기 위해서에요.

예를 들어 [0, 0, 1, 1, 1, 1, 2] 에서

1이 처음 나타나는 위치를 찾고 싶다면,

binarySearch를 통해 1에서 0.5를 뺀 0.5를 검색합니다. 정수 배열에서 실수를 검색했으니 당연히 일치하는 값이 안 나오겠죠? (정수의 범위가 크지 않아서 오차가 나지 않을 거에요)

일치하는 값이 나오지 않는다면, "Return the index of the element, if it is contained in the list within the specified range; otherwise, the inverted insertion point (-insertion point - 1)" 이렇게 삽입해야 할 위치를 음수로 반환합니다. 0에 삽입해야 한다면 -1, 1에 삽입해야 한다면 -2, ... 이런 식으로요.

해당 예시에서는 0.5가 삽입되어야 할 위치는 2이니 -3이 반환되겠네요.

그래서 리턴 값 index에 대해 -(index+1)을 구해주면, 원본 인덱스인 2가 나오게 됩니다.

결벽증이 있어서 전 그냥 클래스로 만들었습니다..

아예 처음부터 실수 배열에 넣는 게 더 빠르고 메모리도 덜 먹을 거에요

댓글을 작성하려면 로그인해야 합니다.