10.4 크기를 모르는 정렬된 원소 탐색

문제

배열과 비슷하지만 size 메서드가 없는 Listy라는 자료구조가 있다. 여기에는 i 인덱스에 위치한 원소를 O(1) 시간에 알 수 있는 elementAt(i) 메서드가 존재한다. 만약 i가 배열의 범위를 넘어섰다면 -1를 반환한다. (이 때문에 이 자료구조는 양의 정수만 지원한다.)

양의 정수가 정렬된 Listy가 주어졌을때 원소 x의 인덱스를 찾는 알고리즘을 작성하라. 만약 x가 여러번 등장한다면 아무거나 반환하면 된다.

 

접근법

이것도 이진탐색법을 이용하면 문제가 해결될 것이다.

우선 배열의 size를 알려면 어떻게 하면 될까? 순차적으로 탐색을 할 수도 있지만 1,2,4,8,16 두배씩 늘려서 찾는다면 logN의 시간에 탐색이 가능할 것이다. 

인덱스를 두배씩 늘리면서 탐색하다가 elementAt(i)값이 -1 인 경우에는 더이상 오른쪽을 찾아 볼 필요가 없으니 왼쪽에 대해서 이진탐색을 진행하면 될것이고 , 만약 elementAt(i)값이 target값보다 크면 사이즈에 상관없이 그부분 부터 그부분/2까지 사이의 범위에서 이진탐색을 진행해도 될 것이다. 왜냐하면 두배씩 증가하고 있고 두배 이전의 값은 target보다 작았기 때문에 탐색할 필요가 없다.

 

def Solution(listy, target):
    index = 1
    while listy.elementAt(index) != -1 and listy.elementAt(index) < target:
        index *=2
    return binarySearch(listy, index/2, index, target)
    
def binarySearch(listy, left, right, target):
    
    while left <= right:
        mid = (left+right)//2
        if target == listy.elementAt(mid) :
            return mid
        elif target < listy.elementAt(mid):
            right = mid -1
        else :
            left = mid +1
    return -1