[C++/26168] 배열 전체 탐색하기

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

이분탐색으로 문제를 해결합니다. 7월에는 블로그에 글을 안올렸지만, 사실 문제는 꾸준히 쉬운 레벨이여도 생소한 문제를 보면 바로 문제를 풀었습니다. 이 문제는 오랜만에 이분탐색을 풀면서 중복되는 값의 첫번째 값과 마지막 값을 구할 수 있다는 것을 처음 알았습니다(?) 이분 탐색 문제는 아주 오랜만에 풀어서 굉장히 시간이 오래걸렸습니다.

아래는 정답코드입니다. 이 문제는 추후에 다시 해결하면서 다시 이분탐색을 자유자재로 써볼 수 있게 구현해봐야겠습니다.

#include<iostream>
#include<algorithm>

#define MAX 100100
using namespace std;

// 끝과 끝일떄 문제 26168 

int n,m;
long long board[MAX];

void init() {
   
   cin >> n >> m;
   
   for(int i = 0; i < n; i++){
      cin >> board[i];
   }
   
   sort(board,board + n);
   
}

// k보다 크거나 같은 
int binarySearch(long long findNumber) {
   
   int startIdx = -1; int endIdx = n;
	
	while(startIdx + 1 < endIdx){
		
		int mid = (startIdx + endIdx) / 2;
		
		if(board[mid] >= findNumber){
			endIdx = mid;
		} else {
			startIdx = mid;
		}
		
	}
   
   	return endIdx;
}

int binarySearch2(long long findNumber) {
   
      int startIdx = -1; int endIdx = n;
	
	while(startIdx + 1 < endIdx){
		
		int mid = (startIdx + endIdx) / 2;
		
		if(board[mid] <= findNumber){
			startIdx = mid;
		} else {
			endIdx = mid;
		}
		
	}
   
   	return endIdx;
}



void solve() {
   
   int order;
   long long k;
   
   while(m--) {
      
      cin >> order;
	   
      if(order == 1) {
      
         cin >> k;
         int start = binarySearch(k);
         cout << n - start<< "\n";
         
         
      } else if(order == 2) {
         
         cin >> k;
         int start = binarySearch(k + 1);
         cout << n - start << "\n";
      
      } else if(order == 3) {
         
         long long s,e; cin >> s >> e;
         int start = binarySearch(s);
         int end = binarySearch2(e);
         //cout << "end : " <<end << " " << "start : " <<start << "\n";
         cout << end - start << "\n";
     
      }
      
   }
   
}

int main() {
	ios_base :: sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
   init();
   solve();
   
   return 0;
}