[PS] binary search 정리

binary search, 이분법적으로 딱 ' 이 시간. 이 숫자. 이 갯수 '를 구하고 싶을 때 매우 강력한 툴이다.
하지만 너무 생각할 게 많다.. 그래서 꾸준히 정리를 해보도록 하겠다!!!
(자꾸 끼워 맞추면서 풀다가 실전에서 시간 너무 오래 잡지 말자...)

[1, 2, 3, 3, 3, 3, 4, 5, 5]  라는 배열이 있다.
우리는 3을 찾고 싶다.
음.. 3 중에서도 가장 최소의 index를 가지는 3을 찾고 싶다면, 이렇게 mid가 가장 왼쪽을 향하게 하도록 극한으로 몰아세운다. (직접 해보면 이해 잘 됨)

while lo<hi:
	mid=(lo+hi)//2
    if arr[mid]<target: lo=mid+1
    else: hi=mid
return lo

반대로, 3중에서 최소의 index를 가지는 3을 찾고 싶으면 반대로 몰아세운다.

while lo<hi:
	mid=(lo+hi)//2
    if arr[mid]>target: hi=mid
    else: lo=mid+1
return hi-1

 

이번에는
[1, 2, 3, 3, 5, 6, 9, 10, 14, 15, 17, 18, 23]에서 i가 속하는 곳을(index를 찾고싶다) -이 때 맨 왼쪽 / 맨 오른쪽에 속하는 경우는 따로 생각한다.
만약 i가 12라고 하면 다음과 같이 찾으면 된다.

def binary_search(array, target, start, end):
    mid = (start+end) //2
    if start==end: return start
    if (array[mid] < target and array[mid+1] > target) or array[mid]==target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid)
    #중간값의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    elif array[mid] < target:
        return binary_search(array, target, mid, end)

---

binary search 구현 시, mid의 입장에도 서보고,, ans의 입장에 서보자.. 

ans의 입장에 서보자.
ans는 mid가 될 수도, low가 될 수도, high가 될 수도 있다.
다음 코드와 같이 우리는 mid로 어떤 조건을 판단한 후 ans를 중간에 도출시킬 수 있다.

while lo<hi:
        #check함수로 판단하여 ans를 도출
        ans=max(ans, mid)
        ans=mid; break;
        l=mid+1
        r=mid-1

while문 조건은 lo<hi , lo<=hi 가 될 수 있다.
https://www.youtube.com/watch?v=7jci-yQhGho
우연히 찾은 이 영상에서 도움을 많이 얻었는데, arr안에서 값을 무조건 찾아야 한다면 lo<=hi를 쓰는 것이 낫다. 배열 속 원소가 1개 또는 배열 속 원소가 2개라면 아예 찾지 못하는 경우가 발생하기 때문.

이렇게 하지 않고 그냥 0~6억까지에서 찾아야 하는 상황이라면 그냥 lo<hi를 써도 될 것 같다.
그리고 lo=mid, hi=mid / lo=mid+1, hi=mid-1 등으로 조절하는 방법을 쓸 수도 있겠다.

결론....!!

내가 생각한 답은?
공식화해서 룰로 생각하지 말고

어차피 비교대상은 arr[mid] 와 target이다.
그 target값보다 큰 걸 만날 경우,
작은 걸 만날 경우,
같은 걸 만날 경우,

그리고 만난 후, lo, hi, mid의 변화 양상(역전이 되는가 아니면 하나로 모이는가)을 생각하면서 짜면 된다!!! 
(그 때 그 때 너무 달라서 훈련+머리 말고는 답 없어보임 정 안되면 그냥 로직 몇 개 없으니까 정리라도 잘해두자)