이진탐색 / lower-bound

이진탐색은 O(logn)의 실행 시간을 갖는다. 매우 유용하기 때문에 잘 기억하도록 하자 응용이 가능하기 떄문이다... 하지만 아래 코드는 같은 수가 반복되어 있으면 찾기가 애매해진다. #include using namespace std; int function(); int main(){ int s= 0; int e = INT_MAX; int find = 1235124; while(s find){ e = mid-1; } else{ return s; } } return not find } find의 lower bound는 배열에서 find보다 작지 않은 첫 번째 값의 인덱스를 반환한다. left-bound를 이용해서 다음과 같은 상황의 문제를 풀 수 있다. 주어진 배열에서 7의 개수는 몇개인가? 1. le..

2022.05.08