fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.  
  6.  
  7. /*
  8. 					vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  9.  
  10.  
  11. 	rend(v)	  begin(v)												rbegin(v)  end(v)
  12. 		.		.														.		.
  13. 		|		|														|		|
  14. 		V		V														V		V
  15. 	+--------------------------------------------------------------------------------+
  16. 	| start |	1	|	3	|	.	.	.	.  key	.	.	.	.	|	12	| finish |
  17. 	+--------------------------------------------------------------------------------+
  18.  
  19. 	Declaring forward iterator : vector<int>::iterator itr;
  20. 	Declaring reverse iterator : vector<int>::reverse_iterator itr;
  21.  
  22. */		
  23.  
  24. 	/*
  25. 	 * lower_bound(key) : 
  26. 	 * 
  27. 	 *  Works only on "sorted" vector or set
  28. 	 *
  29. 	 *	On ascending sorted vector,
  30. 	 *	*lower_bound(begin(v), end(v), key)	returns First Element >= key	
  31. 	 *
  32. 	 *  On descending sorted vector,
  33. 	 *	*lower_bound(begin(v), end(v), key, greater<int>())	returns First Element <= key
  34. 	 */
  35.  
  36. 	/*
  37. 	 * upper_bound(key)	: First element strictly greater than key 
  38. 	 * 
  39. 	 *  Works only on "sorted" vector or set.
  40. 	 * 
  41. 	 *	On ascending sorted vector,
  42. 	 *	*upper_bound(begin(v), end(v), key)	returns First Element > key	
  43. 	 *
  44. 	 *  On descending sorted vector,
  45. 	 *	*upper_bound(begin(v), end(v), key, greater<int>())	returns	First Element < key
  46. 	 *
  47. 	 */
  48.  
  49.  
  50. /// FOR ASCENDING SORTED ARRAY
  51. /////////////////////////////////////////////////////////////////////////////////////
  52.  
  53. 	/*		LAST ELEMENT STRICTLY SMALLER THAN THE KEY VALUE		*/
  54.  
  55. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  56. 	int key = 1;
  57. 	auto it = upper_bound(rbegin(v), rend(v), key, greater<int>());
  58. 	if(it == rend(v)){
  59. 		cout << "No Such Element!!\n";
  60. 	}else{
  61. 		cout << "Last Element Strictly Smaller than key : " << *it << "\n";
  62. 	}
  63.  
  64. 	/*		COUNT OF ELEMENTS STRICTLY SMALLER THAN THE KEY VALUE	*/
  65.  
  66. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  67. 	int key = 7;
  68. 	int cnt = lower_bound(begin(v), end(v), key) - v.begin();
  69. 	cout << "Count of Elements Strictly Smaller than key : " << cnt << "\n";
  70.  
  71. /////////////////////////////////////////////////////////////////////////////////////
  72.  
  73. 	/*		FIRST ELEMENT STRICTLY GREATER THAN THE KEY VALUE		*/
  74.  
  75. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  76. 	int key = 12;
  77. 	auto it = upper_bound(begin(v), end(v), key);
  78. 	if(it == end(v)){
  79. 		cout << "No Element!!\n";
  80. 	}else{
  81. 		cout << "First Element Strictly Greater than key : " << *it << "\n";
  82. 	}
  83.  
  84. 	/*		COUNT OF ELEMENTS STRICTLY GREATER THAN THE KEY VALUE	*/
  85.  
  86. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  87. 	int key = 6;
  88. 	int cnt = end(v) - upper_bound(begin(v), end(v), key);
  89. 	cout << "Count of Elements Strictly Greater than key : " << cnt << "\n";
  90.  
  91.  
  92. /////////////////////////////////////////////////////////////////////////////////////
  93.  
  94. 	/*		LAST ELEMENT SMALLER THAN OR EQUAL TO THE KEY VALUE		*/
  95.  
  96. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  97. 	int key = 15;
  98. 	auto it = lower_bound(rbegin(v), rend(v), key, greater<int>());
  99. 	if(it == rend(v)){
  100. 		cout << "No Element!!\n";
  101. 	}else{
  102. 		cout << "Last Element Smaller than or equal to key : " << *it << "\n";
  103. 	}
  104.  
  105. 	/*		COUNT OF ELEMENTS SMALLER THAN OR EQUAL TO THE KEY VALUE		*/
  106.  
  107. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  108. 	int key = 12;
  109. 	int cnt = upper_bound(begin(v), end(v), key) - begin(v);
  110. 	cout << "Count of Elements Smaller than or equal to key : " << cnt << "\n";
  111.  
  112. /////////////////////////////////////////////////////////////////////////////////////
  113.  
  114. 	/*		FIRST ELEMENT GREATER THAN OR EQUAL TO THE KEY VALUE		*/
  115.  
  116. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  117. 	int key = 11;
  118. 	auto it = lower_bound(begin(v), end(v), key);
  119. 	if(it == end(v)){
  120. 		cout << "No Element!!\n";
  121. 	}else{
  122. 		cout << "First Element Greater than or equal to key : " << *it << "\n";
  123. 	}
  124.  
  125. 	/*		COUNT OF ELEMENTS GREATER THAN OR EQUAL TO THE KEY VALUE		*/
  126.  
  127. 	vector<int> v = {1, 3, 5, 7, 7, 8, 9, 9, 10, 12};
  128. 	int key = 6;
  129. 	int cnt = end(v) - lower_bound(begin(v), end(v), key);
  130. 	cout << "Count of Elements Greater than or equal to key : " << cnt << "\n";
  131.  
  132. /////////////////////////////////////////////////////////////////////////////////////
  133.  
  134.  
  135. /// FOR DESCENDING SORTED ARRAY
  136. /////////////////////////////////////////////////////////////////////////////////////
  137.  
  138. 	/*		FIRST ELEMENT STRICTLY SMALLER THAN THE KEY VALUE		*/
  139.  
  140. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  141. 	int key = 11;
  142. 	auto it = upper_bound(begin(v), end(v), key, greater<int>());
  143. 	if(it == end(v)){
  144. 		cout << "No Such Element!!\n";
  145. 	}else{
  146. 		cout << "First Element Strictly Smaller than key : " << *it << "\n";
  147. 	}
  148.  
  149. 	/*		COUNT OF ELEMENTS STRICTLY SMALLER THAN THE KEY VALUE	*/
  150.  
  151. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  152. 	int key = 12;
  153. 	int cnt = end(v) - upper_bound(begin(v), end(v), key, greater<int>());
  154. 	cout << "Count of Elements Strictly Smaller than key : " << cnt << "\n";
  155.  
  156. /////////////////////////////////////////////////////////////////////////////////////
  157.  
  158. 	/*		LAST ELEMENT STRICTLY GREATER THAN THE KEY VALUE		*/
  159.  
  160. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  161. 	int key = -25;
  162. 	auto it = upper_bound(rbegin(v), rend(v), key);
  163. 	if(it == rend(v)){
  164. 		cout << "No Element!!\n";
  165. 	}else{
  166. 		cout << "Last Element Strictly Greater than key : " << *it << "\n";
  167. 	}
  168.  
  169. 	/*		COUNT OF ELEMENTS STRICTLY GREATER THAN THE KEY VALUE	*/
  170.  
  171. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  172. 	int key = 1;
  173. 	int cnt = rend(v) - upper_bound(rbegin(v), rend(v), key);
  174. 	cout << "Count of Elements Strictly Greater than key : " << cnt << "\n";
  175.  
  176.  
  177. /////////////////////////////////////////////////////////////////////////////////////
  178.  
  179. 	/*		FIRST ELEMENT SMALLER THAN OR EQUAL TO THE KEY VALUE		*/
  180.  
  181. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  182. 	int key = 9;
  183. 	auto it = lower_bound(begin(v), end(v), key, greater<int>());
  184. 	if(it == end(v)){
  185. 		cout << "No Element!!\n";
  186. 	}else{
  187. 		cout << "First Element Smaller than or equal to key : " << *it << "\n";
  188. 	}
  189.  
  190. 	/*		COUNT OF ELEMENTS SMALLER THAN OR EQUAL TO THE KEY VALUE		*/
  191.  
  192. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  193. 	int key = 9;
  194. 	int cnt = end(v) - lower_bound(begin(v), end(v), key, greater<int>());
  195. 	cout << "Count of Elements Smaller than or equal to key : " << cnt << "\n";
  196.  
  197. /////////////////////////////////////////////////////////////////////////////////////
  198.  
  199. 	/*		LAST ELEMENT GREATER THAN OR EQUAL TO THE KEY VALUE		*/
  200.  
  201. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  202. 	int key = 13;
  203. 	auto it = lower_bound(rbegin(v), rend(v), key);
  204. 	if(it == rend(v)){
  205. 		cout << "No Element!!\n";
  206. 	}else{
  207. 		cout << "Last Element Greater than or equal to key : " << *it << "\n";
  208. 	}
  209.  
  210. 	/*		COUNT OF ELEMENTS GREATER THAN OR EQUAL TO THE KEY VALUE		*/
  211.  
  212. 	vector<int> v = {12, 10, 9, 9, 8, 7, 7, 5, 3, 1};
  213. 	int key = 1;
  214. 	int cnt = rend(v) - lower_bound(rbegin(v), rend(v), key);
  215. 	cout << "Count of Elements Greater than or equal to key : " << cnt << "\n";
  216.  
  217. /////////////////////////////////////////////////////////////////////////////////////
  218.  
  219. 	return 0;
  220. }
Success #stdin #stdout 0s 4280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VUvq5G
LOWER and UPPER BOUND on VECTORS
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!