Find Kth Element in Sorted Array

 avatar
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