프로그래밍 면접 문제 17: Search Unknown Length Array
프로그래밍 면접 문제 17: Search Unknown Length Array
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 16: Anagram Strings
길이를 모르는 정렬된 배열과 찾아야 하는 숫자가 주어지면 배열에서 해당 숫자의 인덱스(index)를 반환하는 기능을 구현하는 문제입니다. 범위를 벗어난 요소에 접근하면 예외를 발생시킵니다. 찾는 숫자가 여러 개 존재하는 경우, 여러 인덱스 중 아무 인덱스나 반환합니다. 찾는 숫자가 배열에 존재하지 않으면 -1을 반환합니다.
간단한 해결방법은 배열을 선형적으로 순회하면서 숫자를 찾고, 범위를 벗어나면 예외를 발생시키는 것입니다. 전자의 경우 해당 인덱스를 반환하고, 후자의 경우에는 -1을 반환합니다. 이 해결방법의 복잡도는 O(N)이며, 여기에서 N은 배열에 존재하는 요소의 수이며, 이는 미리 알 수 없습니다. 하지만, 이 접근 방법에서는 정렬된 배열의 장점을 얻을 수 없습니다. 따라서 이진 탐색을 사용하면, 정렬된 순서의 이점을 얻을 수 있습니다.
하지만 배열의 크기를 미리 알 수 없어, 최고 인덱스 제한 값을 제공할 수 없기 때문에 표준 이진 탐색은 동작하지 않습니다. 따라서 배열의 크기와 배열 요소 자체에 대한 일방 이진 탐색(one-sided binary search)을 동시에 수행합니다. 값 K를 찾는다고 가정해 보겠습니다. 루프에서 예외가 발생하거나 K 보다 큰 요소를 찾을 때까지 0, 1, 2, 4, 8, 16, …, 2^N 배열 인덱스를 확인합니다. 값이 K보다 작으면 계속 진행하고(continue), 운좋게 값 K를 찾으면 해당 인덱스를 반환합니다.
인덱스 2^m에서 K 보다 큰 값을 확인한 경우에는 배열이 정렬되어 있기 때문에, 값 K는(존재하는 경우) 반드시 2^(m-1)+1과 2^m-1(포함) 사이에 존재한다는 의미가 됩니다. 예외가 발생한 경우에도 2^(m-1)이 K보다 작다는 것을 알고 해당 인덱스로 접근했을 때는 예외가 발생하지 않는 다는 것을 알기 때문에 위와 동일합니다. 2^m에서 예외가 발생한 경우에는, 배열이 2^(m-1)과 2^m-1 사이의 크기를 갖는다는 의미입니다. 두 경우 모두, 루프를 중단 시키고, 2^(m-1)과 2^m-1 사이의 범위에서 다른 버전의 이진 탐색을 시작합니다. 이전에 인덱스 2^m에서 예외가 발생한 경우, 이진 탐색 중에 더 많은 예외가 발생할 수 있기 때문에 최고 인덱스 제한 값을 해당 위치에 할당해가면서 이를 처리해야 합니다. 다음 코드를 통해 지금까지 설명한 내용을 구현해 보겠습니다.
def getIndex(arr, num):
#check array indexes 0, 2^0, 2^1, 2^2, ...
index, exp = 0, 0
while True:
try:
if arr[index]==num:
return index
elif arr[index]<num:
index=2**exp
exp+=1
else:
break
except IndexError:
break
#Binary Search
left=(index/2)+1
right=index-1
while left<=right:
try:
mid=left+(right-left)/2
if arr[mid]==num:
return mid
elif arr[mid]<num:
left=mid+1
else:
right=mid-1
except IndexError:
right=mid-1
return -1
모든 경우에서 이진 탐색을 사용했고 선형 탐색을 수행하지 않기 때문에, 이 방법의 복잡도는 O(logN) 입니다. 그리고 이 방법은 최적의 방법입니다. 이진 탐색은 가장 중요한 알고리즘 중 하나이며 이 문제는 이진 탐색의 흥미로운 사용법을 보여줍니다.
