Find Kth Element in Sorted Array
unknown
plain_text
a year ago
2.7 kB
6
Indexable
//{ 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
Editor is loading...
Leave a Comment