# Find Kth Element in Sorted Array

unknown
plain_text
a month ago
2.7 kB
2
Indexable
Never
```//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution{
public:
int findLeftMidPosition(int arr[], int lowerBound, int upperBound, int searchElement) {
int ans = -1;
while (lowerBound <= upperBound) {
int mid = (lowerBound + upperBound) >> 1;
if (arr[mid] < searchElement) {
ans = mid;
lowerBound = mid+1;
} else {
upperBound = mid-1;
}
}
return ans;
}

int findRightMidPosition(int arr[], int lowerBound, int upperBound, int searchElement) {
int ans = 0;
while (lowerBound <= upperBound) {
int mid = (lowerBound + upperBound) >> 1;
if (arr[mid] <= searchElement) {
ans = mid;
lowerBound = mid+1;
} else {
upperBound = mid-1;
}
}
return ans;
}

int findKthElement(int firstArr[], int secondArr[], int n, int m, int k) {
int firstLb, secondLb, firstUb, secondUb;
firstLb = secondLb = 0;
firstUb = n-1;
secondUb = m-1;
while (firstLb <= firstUb) {
// cout<<firstLb<<" "<<firstUb<<endl;
int mid = (firstLb + firstUb)>>1;
int leftElementPosition = findLeftMidPosition(secondArr, secondLb, secondUb, firstArr[mid]);
int rightElementPosition = findRightMidPosition(secondArr, secondLb, secondUb, firstArr[mid]);
// cout<<"Element:"<<firstArr[mid]<<" "<<leftElementPosition<<" "<<rightElementPosition<<endl;
if(leftElementPosition + mid + 2 == k) {
return firstArr[mid];
}

if (leftElementPosition + mid + 2 <= k && rightElementPosition + mid + 2 >=k
&& firstArr[mid] == secondArr[rightElementPosition]) {
return firstArr[mid];
}
if (leftElementPosition + mid + 2 < k) {
firstLb = mid+1;
} else {
firstUb = mid-1;
}
}
return -1;
}

int kthElement(int arr1[], int arr2[], int n, int m, int k)
{
int ans = findKthElement(arr1, arr2, n, m, k);
if (ans == -1) {
ans = findKthElement(arr2, arr1, m, n, k);
}
return ans;
}
};

//{ Driver Code Starts.

// Driver code
int main()
{
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
int arr1[n],arr2[m];
for(int i=0;i<n;i++)
cin>>arr1[i];
for(int i=0;i<m;i++)
cin>>arr2[i];

Solution ob;
cout << ob.kthElement(arr1, arr2, n, m, k)<<endl;
}
return 0;
}
// } Driver Code Ends```
Leave a Comment