[Divide and Conquer] 이진 탐색 알고리즘

이진탐색은 정렬되어(올림차순 가정하여)있는 배열에서 원하는 값을 효율적으로 찾는 방법이다. 시간복잡도는 O( logn ).

문제를 풀다보니 이진탐색을 사용하는 경우는 다음이 있는 것 같다. 

개인적으로 세가지 경우 알고리즘이 조금씩 달라서 헷갈린다..넹글넹글.. 그래서 오늘 이후로 헷갈리지 않겠다고 정리해본다.

일단 이진탐색 알고리즘에 대해 알고가야 하는 것. start 인덱스와 end 인덱스가 역전될때까지 진행한다.

---

정확한 일치값 찾는 이진 탐색

# 재귀 호출 버전
def binarySearch(start, end, x):
    if start <= end:
        mid = (start + end) // 2
        
        if x == list[mid]:
            return True # 탐색 성공
        elif x < list[mid]:
            return binarySearch(start, mid-1, x)
        elif x > list[mid]:
            return binarySearch(mid+1, end, x)
            
    return False # 탐색 실패

# 루프 알고리즘 버전

start, end = 0, N-1

while start <= end:
    mid = (start + end) // 2
    
    if x == list[mid]:
        return True
    elif x < list[mid]:
        end = mid - 1
    elif x > list[mid]:
        start = mid + 1
        
return False # 탐색 실패

답이 되는 것 중 최댓값 찾는 이진 탐색 (limit superior)

최댓값을 찾는 경우이니 오름차순 정렬 배열을 기준으로, 되는 것을 발견하면 오른쪽으로 가려는 경향이 있을 것이다. 

Thorough 하게 그림으로 보면 다음과 같다. 초록색이 답이 되는 경우, 회색이 답이 안되는 경우.

물음표는 mid 부분

여기까지는 쉽다. 그런데 역전되는 순간을 바로 상상하기가 쉽지 않다. 그래서 그려보면, 이러나 저러나 end가 가리키는 부분이 답이 된다는 것을 알 수 있다.

역전되는 순간. 결국 end가 답을 가지고 있을 것

이부분을 체감상 확 느끼도록 설명하면

답의 후보를 찾으면 자꾸 답이 없을 수도 있는 곳인 오른쪽으로 스타트를 보내니, 알고리즘이 끝나면 start는 답이 아닌것을 가리키고 있을 것. 그래서 end가 답을 가지고 있겠지.

 

이것보다 와닿게 말을 정리하기 어렵다.

 

그래서 요약하자면

1.  mid 가 답이 되네? 스타트 mid 오른쪽으로 보내

     (mid 답이 안되네? 엔드 mid 왼쪽으로 줄여)

2. 알고리즘 끝나면 start바로 옆 (end)이 답 가지고 있겠네

 

 

답이 되는 것 중 최솟값 찾기 (limit inferior)

same goes for reverse

답이 되는 것을 찾으면 자꾸 end를 답이 없을 만한 왼쪽으로 보내니 나중에는 start가 답을 가지고 있을 것이다.

---