[알고리즘] 상한가, 하한가 구하기 (이진 탐색 활용)
mini_min
상한가,하한가 구하기 💡 이진 탐색으로 상한가와 하한가를 구해서 원하는 숫자를 출력하자. - 백준 10816번- ‘중복 원수의 개수’ 를 알아내고 싶을 때, 중복 원소의 왼쪽 끝과 오른쪽 끝의 인덱스를 알아내서 계산하면 된다. 이진 탐색 개념을 이용하기에 배열은 사전 정렬 되어있어야 한다. 방법 찾으려는 값의 하한선, 상한선을 따로 구할 생각을 하자. 하한선은 찾으려는 값 이상의 값이 나타난 위치다. “이상” 이란 같거나 큰 수를 뜻한다. 상한선은 찾으려는 값의 초과 값이 나타난 위치다. “초과” 란 보다 큰 수를 뜻한다. 상한가, 하한가 예시 정렬된 배열에서 ‘숫자 10의 상한가, 하한가를 찾는다. (하한선은 최초 10 이 나오는 위치인 3, 상한선은 10을 넘어서는 최초 위치 6 이 나와야 한다.) ..