[알고리즘] 등차수열의 합과 이진 탐색(Binary Search)

int ans = 0;
while(left <= right)
{
    int mid = (left + right) / 2;
    long sum = (long)mid * (mid + 1) / 2;
    
    if(sum <= S)
    {
        ans = mid;
        left = mid + 1;
    }
    else
        right = mid - 1;
}

 

1보다 mid까지의 합이 S 값보다 크지 않으면서 가장 큰 mid의 값을 찾는 과정

 

등차수열의 합 공식

https://m.blog.naver.com/pso164/222813745817

((첫항 + 마지막항) / 2) * 개수는 즉, mid * 개수인데, 여기에서처럼 1부터 mid까지는 개수가 (mid+1)이 되어 (mid*(mid+1))/2로 표현된다. 공식으로 접근할 생각을 못 했어서 저런 수식이 있길래 한참을 들여다 봤는데 등차수열의 합이었다. 어이는 없었지만 덕분에 1~mid의 합을 이진 탐색으로도 생각해 볼 수 있어서 좋았다. 그리고 아래는 똑같이 등차수열의 합 공식을 다루지만 접근법이 새로워서 한번 참고해 보면 좋을 것 같다. 수들을 도형으로 표현해 넓이 구하는 공식으로 구하였다. 결론적으로는 이 공식으로 귀결된다.  

 

[참고: https://adgw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1-n%EA%B9%8C%EC%A7%80-%ED%95%A9%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%9B%90%EB%A6%AC]

[알고리즘] 1 ~ n까지 합을 구하는 원리

이진 탐색 (Binary Search)

• 탐색 범위를 반으로 나누어 찾는 값을 포함하는 범위를 좁혀가는 방식
• 주로 배열의 인덱스를 기준으로 배열 내 값을 탐색 (리스트나 트리에서도 가능)
• 원소들이 정렬된 구조에서만 사용할 수 있음
• 한번에 바로 찾는다면 O(1), 평균/최악의 경우 O(logN)
• 선형 탐색(O(N))보다는 속도가 빠름

https://medium.com/@hjjun1123/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B6%95%EC%86%8C-%EC%A0%95%EB%B3%B5-decrease-and-conquer-c1f8e2b7bfe9

 

[참고:https://velog.io/@kwontae1313/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89Binary-Search-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B0%9C%EB%85%90,https://medium.com/@hjjun1123/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B6%95%EC%86%8C-%EC%A0%95%EB%B3%B5-decrease-and-conquer-c1f8e2b7bfe9]