forked from souvikg544/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
kthelement.cpp
39 lines (36 loc) · 1.07 KB
/
kthelement.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int kthelement(int arr1[], int arr2[], int m, int n, int k) {
if(m > n) {
return kthelement(arr2, arr1, n, m, k);
}
int low = max(0,k-m), high = min(k,n);
while(low <= high) {
int cut1 = (low + high) >> 1;
int cut2 = k - cut1;
int l1 = cut1 == 0 ? INT_MIN : arr1[cut1 - 1];
int l2 = cut2 == 0 ? INT_MIN : arr2[cut2 - 1];
int r1 = cut1 == n ? INT_MAX : arr1[cut1];
int r2 = cut2 == m ? INT_MAX : arr2[cut2];
if(l1 <= r2 && l2 <= r1) {
return max(l1, l2);
}
else if (l1 > r2) {
high = cut1 - 1;
}
else {
low = cut1 + 1;
}
}
return 1;
}
int main() {
int array1[] = {2,3,6,7,9};
int array2[] = {1,4,8,10};
int m = sizeof(array1)/sizeof(array1[0]);
int n = sizeof(array2)/sizeof(array2[0]);
int k = 5;
cout<<"The element at the kth position in the final sorted array is "
<<kthelement(array1,array2,m,n,k);
return 0;
}