fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. //           0  1  2  3  4  5  6  7  8  9 10 11  12  13  14
  4. int arr[] = {1, 1, 1, 2, 2, 4, 5, 7, 7, 8, 8, 9, 10, 10, 10}, n = 15;
  5. //           L                    M                       R
  6. //           L        M        R
  7. //                                L        M              R
  8.  
  9. int binser_upper(int cari) {
  10. 	// upper bound
  11. 	int L = 0, R = n-1, M = (L+R+1)/2;
  12. 	while(L < R) {
  13. 		if(arr[M] <= cari)
  14. 			L = M;
  15. 		else // arr[M] > cari
  16. 			R = M-1;
  17. 		M = (L+R+1)/2;
  18. 	}
  19.  
  20. 	if(arr[L] == cari)
  21. 		return L;
  22. 	else
  23. 		return -1;
  24. }
  25.  
  26. int binser_lower(int cari) {
  27. 	// lower bound
  28. 	int L = 0, R = n-1, M = (L+R)/2;
  29. 	while(L < R) {
  30. 		if(arr[M] < cari)
  31. 			L = M+1;
  32. 		else // arr[M] >= cari
  33. 			R = M;
  34. 		M = (L+R)/2;
  35. 	}
  36.  
  37. 	if(arr[L] == cari)
  38. 		return L;
  39. 	else
  40. 		return -1;
  41. }
  42.  
  43. int main() {
  44. 	// binary search -> O(log(n))
  45. 	int cari, banyak;
  46. 	while(cin >> cari) {
  47. 		bool ada = (binser_upper(cari) != -1);
  48.  
  49. 		int banyak = binser_upper(cari)-binser_lower(cari)+1;
  50. 		cout << "Banyak angka " << cari << " adalah sebanyak " << (ada?banyak:0) << endl;
  51. 	}
  52.  
  53.  
  54. 	// linear search -> O(n)
  55. 	/*
  56. 	int ans = -1;
  57. 	for(int i = 0; i < n; i++)
  58. 		if(arr[i] == cari)
  59. 			ans = i;
  60. 	if(ans == -1)
  61. 		cout << "Tidak ada" << endl;
  62. 	else
  63. 		cout << "Ada di indeks " << ans << endl;
  64. 	*/
  65. 	return 0;
  66. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
1 2 3 4 5 6 7 8 9 10
stdout
copy 
Banyak angka 1 adalah sebanyak 3
Banyak angka 2 adalah sebanyak 2
Banyak angka 3 adalah sebanyak 0
Banyak angka 4 adalah sebanyak 1
Banyak angka 5 adalah sebanyak 1
Banyak angka 6 adalah sebanyak 0
Banyak angka 7 adalah sebanyak 2
Banyak angka 8 adalah sebanyak 2
Banyak angka 9 adalah sebanyak 1
Banyak angka 10 adalah sebanyak 3
https://ideone.com/ND7AVW
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!