10.5 드문드문 탐색

문제

빈 문자열이 섞여 있는 정렬된 문자열 배열이 주어졌을때, 특정 문자열의 위치르 찾는 메서드를 작성하라.

입력 :"ball' , ["at", "" , "". "", "ball", "", "", "car", "" , "", "",  "dad", "", ""]

 

해결법

빈 문자열이 없었다면 그냥 이진 탐색을 적용하면 될것이다.

이진 탐색을 적용하면서 빈 문자열에 대한 처리를 해주면 해결이 가능할 것이다.

mid가 빈 문자열의 위치한 경우 가장 가까운 word의 위치를 mid로 변경해주고, 이진 탐색을 진행해 나가면 될 것같다.

def Solution(list, target):
    if list is None or target=="" or target ==None :
        return -1
    return findTarget(list, target, left, right)

def findTarget(list, target, left, right):
    if left > right :
        return -1
    
    mid = (left+right)//2
    if list[mid] =="":
        l,r = mid-1, mid+1
        while True:
            if left > l and r > right :
                return -1
            elif right >= r and list[r] != "":
                mid = r
                break
            elif left <= l and list[l] !="":
                mid = l
                break
            else :
                right +=1
                left +=1

    if list[mid] == target:
        return mid
    elif target < list[mid] :
        return findTarget(list, target, left, mid -1)
    elif list[mid] < target :
        return findTarget(list, tatget, mid+1, right)