fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int binarySearch(vector<int>& A, vector<int>& B, int index, int loA, int hiA, int loB, int hiB) {
  7. 	if (loA == hiA && loB == hiB) {
  8. 		if (loA + loB >= index) { // loB is exclusive
  9. 			return min(A[loA], B[loB]);
  10. 		} else {
  11. 			return max(A[loA], B[loB]);
  12. 		}
  13. 	}
  14.  
  15. 	int midA = (loA + hiA + 1) / 2;
  16. 	int midB = upper_bound(B.begin(), B.end(), A[midA]) - B.begin();
  17.  
  18. 	if (midA + midB > index) {
  19. 		return binarySearch(B, A, index, loB, hiB, loA, midA - 1);
  20. 	} else {
  21. 		return binarySearch(B, A, index, loB, hiB, midA, hiA);
  22. 	}
  23.  
  24. }
  25.  
  26. double findMedian(vector<int>& A, vector<int>& B) {
  27.     int totalSize = A.size() + B.size();
  28.     int oddIndex = totalSize / 2;
  29.     int evenIndex = totalSize / 2 - (totalSize % 2 == 0);
  30.  
  31.     int oddBinarySearch = binarySearch(A, B, oddIndex, 0, A.size() - 1, 0, B.size() - 1);
  32.     int evenBinarySearch = binarySearch(A, B, evenIndex, 0, A.size() - 1, 0, B.size() - 1);
  33.  
  34.     return (oddBinarySearch + evenBinarySearch) / 2.0;
  35. }
  36.  
  37.  
  38. int main() {
  39. 	return 0;
  40. }
Success #stdin #stdout 0s 4436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hoC9Tg
language:
C++14 (gcc 8.3)
created:
6 years 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!