대싕이의 내맘대로 블로그

알고리즘 문제를 해결하다보니 이진탐색을 경우에 맞게 변경해야 하는 경우가 생겼다. 정렬된 배열에서 중앙값(median)을 비교하여 검색범위를 절반으로 줄여나가는 방식이다. 따라서 이진탐색은 O(log N)의 성능을 갖는다. 중복이 있는 배열에서 성분 중 가장 앞의 위치를 찾는 법 1. 값 중복 O 2. target이 모든 v에 대해 더 작은 경우 : 0 3. target이 모든 v에 대해 더 큰 경우 : v.size() 4. target이 v안에 없는 경우 : target보다 큰 가장 가까운 v의 인덱스 return 5. 중복된 값이 있는 경우 : 같은 값 중 가장 작은 인덱스 return 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int solution(vector v, in..