Wie findet man das k-kleinste Element in der Vereinigung von zwei sortierten Arrays?

Dies ist eine Hausaufgabenfrage. Sie sagen, es dauert O(logN + logM) wobei N und M die Längen der Arrays sind.

Benennen wir die Arrays a und b . Offensichtlich können wir alle a[i] und b[i] ignorieren, wobei i> k ist.
Lassen Sie uns zuerst a[k/2] und b[k/2] . Sei b[k/2] > a[k/2] . Daher können wir auch alle b[i] vercasting, wobei i> k / 2 ist.

Jetzt haben wir alle a[i] , wobei i <k und alle b[i] , wobei i <k / 2 ist, um die Antwort zu finden.

Was ist der nächste Schritt?

   

    Du hast es, geh einfach weiter! Und sei vorsichtig mit den Indizes …

    Um ein Bit zu vereinfachen, nehme ich an, dass N und M> k sind, also ist die Komplexität hier O (log k), das ist O (log N + log M).

    Pseudocode:

     i = k/2 j = k - i step = k/4 while step > 0 if a[i-1] > b[j-1] i -= step j += step else i += step j -= step step /= 2 if a[i-1] > b[j-1] return a[i-1] else return b[j-1] 

    Für die Demonstration können Sie die Schleifeninvariante i + j = k verwenden, aber ich werde nicht alle Ihre Hausaufgaben machen 🙂

    Ich hoffe, ich beantworte Ihre Hausaufgaben nicht, da diese Frage bereits seit über einem Jahr gestellt wird. Hier ist eine tail rekursive Lösung, die log (len (a) + len (b)) Zeit nimmt.

    Annahme: Die Eingaben sind richtig. dh k liegt im Bereich [0, len (a) + len (b)]

    Basisfälle:

    • Wenn die Länge eines der Arrays 0 ist, ist die Antwort das k-te Element des zweiten Arrays.

    Reduktionsschritte:

    • Wenn der mittlere Index von a + mittlerer Index von b kleiner als k
      • Wenn das mittlere Element von a größer ist als das mittlere Element von b , können wir die erste Hälfte von b ignorieren und k anpassen.
      • sonst ignoriere die erste Hälfte von a , stelle k .
    • Sonst wenn k kleiner ist als die Summe der mittleren Indizes von a und b :
      • Wenn das mittlere Element von a größer als das mittlere Element von b , können wir die zweite Hälfte von a ignorieren
      • sonst können wir die zweite Hälfte von b ignorieren

    Code:

     def kthlargest(arr1, arr2, k): if len(arr1) == 0: return arr2[k] elif len(arr2) == 0: return arr1[k] mida1 = len(arr1)/2 mida2 = len(arr2)/2 if mida1+mida2arr2[mida2]: return kthlargest(arr1, arr2[mida2+1:], k-mida2-1) else: return kthlargest(arr1[mida1+1:], arr2, k-mida1-1) else: if arr1[mida1]>arr2[mida2]: return kthlargest(arr1[:mida1], arr2, k) else: return kthlargest(arr1, arr2[:mida2], k) 

    Bitte beachten Sie, dass meine Lösung bei jedem Aufruf neue Kopien kleinerer Arrays erstellt. Dies kann einfach dadurch behoben werden, dass nur Start- und Endindizes auf den ursprünglichen Arrays übergeben werden.

    Viele Leute antworteten auf diese Frage “kth kleinste Element aus zwei sortierten Arrays”, aber normalerweise nur mit allgemeinen Ideen, nicht mit einem klaren Arbeitscode oder einer Randbedingungenanalyse.

    Hier möchte ich es sorgfältig mit der Art, wie ich ging, um einige Neulinge zu verstehen, mit meinem korrekt arbeitenden Java-Code zu erarbeiten. A1 und A2 sind zwei sortierte aufsteigende Arrays mit den size1 und size2 als Länge. Wir müssen das k-te kleinste Element aus der Vereinigung dieser beiden Arrays finden. Hier nehmen wir vernünftigerweise an, dass (k > 0 && k < = size1 + size2) , was impliziert, dass A1 und A2 nicht beide leer sein können.

    Lassen Sie uns zuerst diese Frage mit einem langsamen O (k) -Algorithmus angehen. Die Methode besteht darin, das erste Element der beiden Arrays A1[0] und A2[0] . Nimm den kleineren, sag A1[0] in unsere Tasche. Dann vergleiche A1[1] mit A2[0] und so weiter. Wiederhole diese Aktion, bis unsere Tasche k Elemente erreicht hat. Ganz wichtig: Im ersten Schritt können wir uns nur auf A1[0] in unserer Tasche festlegen. Wir können A2[0] nicht einschließen oder ausschließen !!!

    Der folgende O (k) Code gibt Ihnen ein Element vor der richtigen Antwort. Hier verwende ich es, um meine Idee zu zeigen und Randbedingung zu analysieren. Ich habe den richtigen Code nach diesem:

     private E kthSmallestSlowWithFault(int k) { int size1 = A1.length, size2 = A2.length; int index1 = 0, index2 = 0; // base case, k == 1 if (k == 1) { if (size1 == 0) { return A2[index2]; } else if (size2 == 0) { return A1[index1]; } else if (A1[index1].compareTo(A2[index2]) < 0) { return A1[index1]; } else { return A2[index2]; } } /* in the next loop, we always assume there is one next element to compare with, so we can * commit to the smaller one. What if the last element is the kth one? */ if (k == size1 + size2) { if (size1 == 0) { return A2[size2 - 1]; } else if (size2 == 0) { return A1[size1 - 1]; } else if (A1[size1 - 1].compareTo(A2[size2 - 1]) < 0) { return A1[size1 - 1]; } else { return A2[size2 - 1]; } } /* * only when k > 1, below loop will execute. In each loop, we commit to one element, till we * reach (index1 + index2 == k - 1) case. But the answer is not correct, always one element * ahead, because we didn't merge base case function into this loop yet. */ int lastElementFromArray = 0; while (index1 + index2 < k - 1) { if (A1[index1].compareTo(A2[index2]) < 0) { index1++; lastElementFromArray = 1; // commit to one element from array A1, but that element is at (index1 - 1)!!! } else { index2++; lastElementFromArray = 2; } } if (lastElementFromArray == 1) { return A1[index1 - 1]; } else { return A2[index2 - 1]; } } 

    Die mächtigste Idee ist, dass wir in jeder Schleife immer den Basisfallansatz verwenden. Nachdem wir uns auf das aktuell kleinste Element festgelegt haben, kommen wir dem Ziel einen Schritt näher: dem k-ten kleinsten Element. Springe niemals in die Mitte und mach dich verwirrt und verloren!

    Durch Beobachten des obigen Code-Basis-Falls k == 1, k == size1+size2 , und kombinieren mit dem A1 und A2 können beide nicht leer sein. Wir können die Logik in einen prägnanteren Stil umwandeln.

    Hier ist ein langsamer aber korrekt funktionierender Code:

     private E kthSmallestSlow(int k) { // System.out.println("this is an O(k) speed algorithm, very concise"); int size1 = A1.length, size2 = A2.length; int index1 = 0, index2 = 0; while (index1 + index2 < k - 1) { if (size1 > index1 && (size2 < = index2 || A1[index1].compareTo(A2[index2]) < 0)) { index1++; // here we commit to original index1 element, not the increment one!!! } else { index2++; } } // below is the (index1 + index2 == k - 1) base case // also eliminate the risk of referring to an element outside of index boundary if (size1 > index1 && (size2 < = index2 || A1[index1].compareTo(A2[index2]) < 0)) { return A1[index1]; } else { return A2[index2]; } } 

    Jetzt können wir einen schnelleren Algorithmus ausprobieren, der bei O läuft (log k). Vergleiche auch A1[k/2] mit A2[k/2] ; Wenn A1[k/2] kleiner ist, sollten alle Elemente von A1[0] bis A1[k/2] in unserer Tasche sein. Die Idee ist, sich nicht nur auf ein Element in jeder Schleife festzulegen; Der erste Schritt enthält k/2 Elemente. Auch hier können wir A2[0] zu A2[k/2] hinzufügen oder ausschließen. Also können wir im ersten Schritt nicht mehr als k/2 Elemente gehen. Für den zweiten Schritt können wir nicht mehr als k/4 Elemente gehen ...

    Nach jedem Schritt kommen wir dem k-ten Element viel näher. Gleichzeitig wird jeder Schritt kleiner und kleiner, bis wir (step == 1) , was (k-1 == index1+index2) . Dann können wir uns wieder auf den einfachen und mächtigen Basisfall beziehen.

    Hier ist der funktionierende Code:

     private E kthSmallestFast(int k) { // System.out.println("this is an O(log k) speed algorithm with meaningful variables name"); int size1 = A1.length, size2 = A2.length; int index1 = 0, index2 = 0, step = 0; while (index1 + index2 < k - 1) { step = (k - index1 - index2) / 2; int step1 = index1 + step; int step2 = index2 + step; if (size1 > step1 - 1 && (size2 < = step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) { index1 = step1; // commit to element at index = step1 - 1 } else { index2 = step2; } } // the base case of (index1 + index2 == k - 1) if (size1 > index1 && (size2 < = index2 || A1[index1].compareTo(A2[index2]) < 0)) { return A1[index1]; } else { return A2[index2]; } } 

    Einige Leute mögen sich Sorgen machen, ob (index1+index2) über k-1 springt? Könnten wir den Basisfall übersehen (k-1 == index1+index2) ? Das ist nicht möglich. Sie können 0,5 + 0,25 + 0,125 ... addieren, und Sie werden nie über 1 hinausgehen.

    Natürlich ist es sehr einfach, den obigen Code in einen rekursiven Algorithmus umzuwandeln:

     private E kthSmallestFastRecur(int k, int index1, int index2, int size1, int size2) { // System.out.println("this is an O(log k) speed algorithm with meaningful variables name"); // the base case of (index1 + index2 == k - 1) if (index1 + index2 == k - 1) { if (size1 > index1 && (size2 < = index2 || A1[index1].compareTo(A2[index2]) < 0)) { return A1[index1]; } else { return A2[index2]; } } int step = (k - index1 - index2) / 2; int step1 = index1 + step; int step2 = index2 + step; if (size1 > step1 - 1 && (size2 < = step2 - 1 || A1[step1 - 1].compareTo(A2[step2 - 1]) < 0)) { index1 = step1; } else { index2 = step2; } return kthSmallestFastRecur(k, index1, index2, size1, size2); } 

    Ich hoffe, die obige Analyse und der Java-Code könnten Ihnen helfen zu verstehen. Aber kopiere niemals meinen Code als Hausaufgabe! Prost ;)

    Hier ist eine C ++ iterative Version von @ Lambdapilgrims Lösung (siehe die Erklärung des Algorithmus dort):

     #include  #include  template typename std::iterator_traits::value_type nsmallest_iter(RandomAccessIterator firsta, RandomAccessIterator lasta, RandomAccessIterator firstb, RandomAccessIterator lastb, size_t n, Compare less) { assert(issorted(firsta, lasta, less) && issorted(firstb, lastb, less)); for ( ; ; ) { assert(n < static_cast((lasta - firsta) + (lastb - firstb))); if (firsta == lasta) return *(firstb + n); if (firstb == lastb) return *(firsta + n); size_t mida = (lasta - firsta) / 2; size_t midb = (lastb - firstb) / 2; if ((mida + midb) < n) { if (less(*(firstb + midb), *(firsta + mida))) { firstb += (midb + 1); n -= (midb + 1); } else { firsta += (mida + 1); n -= (mida + 1); } } else { if (less(*(firstb + midb), *(firsta + mida))) lasta = (firsta + mida); else lastb = (firstb + midb); } } } 

    Es funktioniert für alle 0 < = n < (size(a) + size(b)) Indizes und hat O(log(size(a)) + log(size(b))) Komplexität.

    Beispiel

     #include  // greater<> #include  #define SIZE(a) (sizeof(a) / sizeof(*a)) int main() { int a[] = {5,4,3}; int b[] = {2,1,0}; int k = 1; // find minimum value, the 1st smallest value in a,b int i = k - 1; // convert to zero-based indexing int v = nsmallest_iter(a, a + SIZE(a), b, b + SIZE(b), SIZE(a)+SIZE(b)-1-i, std::greater()); std::cout < < v << std::endl; // -> 0 return v; } 

    Mein Versuch für erste k Zahlen, k-te Zahl in 2 sortierten Feldern und in n sortierten Feldern:

     // require() is recognizable by node.js but not by browser; // for running/debugging in browser, put utils.js and this file in 

    Den vollständigen Code mit Debug-Utils finden Sie unter: https://github.com/brainclone/teasers/tree/master/kth

    Hier ist mein Code basierend auf Jules Olleons Lösung:

     int getNth(vector& v1, vector& v2, int n) { int step = n / 4; int i1 = n / 2; int i2 = n - i1; while(!(v2[i2] >= v1[i1 - 1] && v1[i1] > v2[i2 - 1])) { if (v1[i1 - 1] >= v2[i2 - 1]) { i1 -= step; i2 += step; } else { i1 += step; i2 -= step; } step /= 2; if (!step) step = 1; } if (v1[i1 - 1] >= v2[i2 - 1]) return v1[i1 - 1]; else return v2[i2 - 1]; } int main() { int a1[] = {1,2,3,4,5,6,7,8,9}; int a2[] = {4,6,8,10,12}; //int a1[] = {1,2,3,4,5,6,7,8,9}; //int a2[] = {4,6,8,10,12}; //int a1[] = {1,7,9,10,30}; //int a2[] = {3,5,8,11}; vector v1(a1, a1+9); vector v2(a2, a2+5); cout < < getNth(v1, v2, 5); return 0; } 

    Hier ist meine Implementierung in C, Sie können sich auf @Jules Olléon’s für den Algorithmus erklären: Die Idee hinter dem Algorithmus ist, dass wir i + j = k beibehalten, und so ein i und j finden, dass a [i-1]

     int find_k(int A[], int m, int B[], int n, int k) { if (m < = 0 )return B[k-1]; else if (n <= 0) return A[k-1]; int i = ( m/double (m + n)) * (k-1); if (i < m-1 && i 0) ? A[i-1] : INT_MIN, Ai = (i 0) ? B[j-1] : INT_MIN, Bj = (j= Bj_1 && Ai < = Bj) { return Ai; } else if (Bj >= Ai_1 && Bj < = Ai) { return Bj; } if (Ai < Bj_1) { // the answer can't be within A[0,...,i] return find_k(A+i+1, mi-1, B, n, j); } else { // the answer can't be within A[0,...,i] return find_k(A, m, B+j+1, nj-1, i); } } 

    Hier ist meine Lösung. Der C ++ – Code gibt den k-ten kleinsten Wert sowie die Anzahl der Iterationen aus, um den k-ten kleinsten Wert mit einer Schleife zu erhalten, die meiner Meinung nach in der Reihenfolge log (k) liegt. Der Code erfordert jedoch, dass k kleiner ist als die Länge des ersten Arrays, was eine Beschränkung darstellt.

     #include  #include  #include using namespace std; template comparable kthSmallest(vector & a, vector & b, int k){ int idx1; // Index in the first array a int idx2; // Index in the second array b comparable maxVal, minValPlus; float iter = k; int numIterations = 0; if(k > a.size()){ // Checks if k is larger than the size of first array cout < < " k is larger than the first array" << endl; return -1; } else{ // If all conditions are satisfied, initialize the indexes idx1 = k - 1; idx2 = -1; } for ( ; ; ){ numIterations ++; if(idx2 == -1 || b[idx2] <= a[idx1] ){ maxVal = a[idx1]; minValPlus = b[idx2 + 1]; idx1 = idx1 - ceil(iter/2); // Binary search idx2 = k - idx1 - 2; // Ensures sum of indices = k - 2 } else{ maxVal = b[idx2]; minValPlus = a[idx1 + 1]; idx2 = idx2 - ceil(iter/2); // Binary search idx1 = k - idx2 - 2; // Ensures sum of indices = k - 2 } if(minValPlus >= maxVal){ // Check if kth smallest value has been found cout < < "The number of iterations to find the " << k << "(th) smallest value is " << numIterations << endl; return maxVal; } else iter/=2; // Reduce search space of binary search } } int main(){ //Test Cases vector a = {2, 4, 9, 15, 22, 34, 45, 55, 62, 67, 78, 85}; vector b = {1, 3, 6, 8, 11, 13, 15, 20, 56, 67, 89}; // Input k < a.size() int kthSmallestVal; for (int k = 1; k <= a.size() ; k++){ kthSmallestVal = kthSmallest( a ,b ,k ); cout < < k <<" (th) smallest Value is " << kthSmallestVal << endl << endl << endl; } } 

    Der oben angegebene erste Pseudocode funktioniert nicht für viele Werte. Zum Beispiel, hier sind zwei Arrays. int [] a = {1, 5, 6, 8, 9, 11, 15, 17, 19}; int [] b = {4, 7, 8, 13, 15, 18, 20, 24, 26};

    Es funktionierte nicht für k = 3 und k = 9 darin. Ich habe eine andere Lösung. Es ist unten angegeben.

     private static void traverse(int pt, int len) { int temp = 0; if (len == 1) { int val = 0; while (k - (pt + 1) - 1 > -1 && M[pt] < N[k - (pt + 1) - 1]) { if (val == 0) val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt]; else { int t = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt]; val = val < t ? val : t; } ++pt; } if (val == 0) val = M[pt] < N[k - (pt + 1) - 1] ? N[k - (pt + 1) - 1] : M[pt]; System.out.println(val); return; } temp = len / 2; if (M[pt + temp - 1] < N[k - (pt + temp) - 1]) { traverse(pt + temp, temp); } else { traverse(pt, temp); } } 

    Aber ... es funktioniert auch nicht für k = 5. Es gibt diesen geraden / ungeraden Fang von k, der es nicht einfach macht.

     public class KthSmallestInSortedArray { public static void main(String[] args) { int a1[] = {2, 3, 10, 11, 43, 56}, a2[] = {120, 13, 14, 24, 34, 36}, k = 4; System.out.println(findKthElement(a1, a2, k)); } private static int findKthElement(int a1[], int a2[], int k) { /** Checking k must less than sum of length of both array **/ if (a1.length + a2.length < k) { throw new IllegalArgumentException(); } /** K must be greater than zero **/ if (k <= 0) { throw new IllegalArgumentException(); } /** * Finding begin, l and end such that * begin <= l < end * a1[0].....a1[l-1] and * a2[0]....a2[kl-1] are the smallest k numbers */ int begin = Math.max(0, k - a2.length); int end = Math.min(a1.length, k); while (begin < end) { int l = begin + (end - begin) / 2; /** Can we include a1[l] in the k smallest numbers */ if ((l < a1.length) && (k - l > 0) && (a1[l] < a2[k - l - 1])) { begin = l + 1; } else if ((l > 0) && (k - l < a2.length) && (a1[l - 1] > a2[k - 1])) { /** * This is the case where we can discard * a[l-1] from the set of k smallest numbers */ end = l; } else { /** * We found our answer since both inequalities were * false */ begin = l; break; } } if (begin == 0) { return a2[k - 1]; } else if (begin == k) { return a1[k - 1]; } else { return Math.max(a1[begin - 1], a2[k - begin - 1]); } } } 

    Hier ist meine Lösung in Java. Ich werde versuchen, es weiter zu optimieren

      public class FindKLargestTwoSortedArray { public static void main(String[] args) { int[] arr1 = { 10, 20, 40, 80 }; int[] arr2 = { 15, 35, 50, 75 }; FindKLargestTwoSortedArray(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, 6); } public static void FindKLargestTwoSortedArray(int[] arr1, int start1, int end1, int[] arr2, int start2, int end2, int k) { if ((start1 < = end1 && start1 >= 0 && end1 < arr1.length) && (start2 <= end2 && start2 >= 0 && end2 < arr2.length)) { int midIndex1 = (start1 + (k - 1) / 2); midIndex1 = midIndex1 >= arr1.length ? arr1.length - 1 : midIndex1; int midIndex2 = (start2 + (k - 1) / 2); midIndex2 = midIndex2 >= arr2.length ? arr2.length - 1 : midIndex2; if (arr1[midIndex1] == arr2[midIndex2]) { System.out.println("element is " + arr1[midIndex1]); } else if (arr1[midIndex1] < arr2[midIndex2]) { if (k == 1) { System.out.println("element is " + arr1[midIndex1]); return; } else if (k == 2) { System.out.println("element is " + arr2[midIndex2]); return; }else if (midIndex1 == arr1.length-1 || midIndex2 == arr2.length-1 ) { if(k==(arr1.length+arr2.length)){ System.out.println("element is " + arr2[midIndex2]); return; }else if(k==(arr1.length+arr2.length)-1){ System.out.println("element is " + arr1[midIndex1]); return; } } int remainingElementToSearch = k - (midIndex1-start1); FindKLargestTwoSortedArray( arr1, midIndex1, (midIndex1 + remainingElementToSearch) >= arr1.length ? arr1.length-1 : (midIndex1 + remainingElementToSearch), arr2, start2, midIndex2, remainingElementToSearch); } else if (arr1[midIndex1] > arr2[midIndex2]) { FindKLargestTwoSortedArray(arr2, start2, end2, arr1, start1, end1, k); } } else { return; } } } 

    Dies ist inspiriert von Algo bei wunderbaren Youtube Video

    Link zur Komplexität des Codes (log (n) + log (m))

    Link zum Code (log (n) * log (m))

    Implementierung von (log (n) + log (m)) Lösung

    Ich möchte meine Erklärung dem Problem hinzufügen. Dies ist ein klassisches Problem, bei dem wir die Tatsache verwenden müssen, dass die beiden Arrays sortiert sind. Wir haben zwei sortierte Arrays arr1 der Größe sz1 und arr2 der Größe sz2 erhalten

    a) Nehmen wir an, wenn

    Überprüfen ob k gültig ist

    k ist> (sz1 + sz2)

    dann können wir kth kleinstes Element in der Vereinigung von beiden sortierten Feldern nicht finden ryt Also ungültige Daten zurückgeben. b) Wenn nun die obige Bedingung falsch ist und wir einen gültigen und durchführbaren Wert von k haben,

    Edge-Cases verwalten

    Wir werden beide Arrays mit -infinity-Werten an den Front- und + unendlich-Werten am Ende anhängen, um die Kantenfälle von k = 1,2 und k = (sz1 + sz2-1), (sz1 + sz2) usw. zu überdecken.

    Jetzt haben beide Arrays die Größe (sz1 + 2) bzw. (sz2 + 2)

    Hauptalgorithmus

    Jetzt werden wir eine binäre Suche nach arr1 durchführen. Wir werden eine binäre Suche nach arr1 durchführen, die nach einem Index i sucht, startIndex < = i <= endIndex

    so dass, wenn wir den entsprechenden Index j in arr2 unter Verwendung der Einschränkung {(i + j) = k} finden, dann if

    if (arr2 [j-1] , dann ist arr1 [i] das k-kleinste (Fall 1)

    sonst wenn (arr1 [i-1] , dann ist arr2 [i] das k-kleinste (Fall 2)

    else bedeutet entweder arr1 [i] (Fall3)

    oder arr2 [j-1] (Fall4)

    Da wir wissen, dass das k-kleinste Element (k-1) Elemente kleiner als es in der Vereinigung der beiden Arrays ryt hat? Damit,

    In Case1 , was wir getan haben, haben wir sichergestellt, dass es insgesamt (k-1) kleinere Elemente zu arr1 [i] gibt, weil Elemente kleiner als arr1 [i] in arr1 Array i-1 in der Anzahl sind, wie wir wissen (arr2 [ j-1]

    Aber die Antwort kommt vielleicht nicht immer aus dem ersten Array, dh arr1, also haben wir nach case2 gesucht, das auch ähnlich wie Fall 1 erfüllt, weil (i-1) + (j-1) = (k-1). Wenn wir nun (arr1 [i-1]

    Um in Fall3 entweder einen Fall 1 oder einen Fall 2 zu bilden, müssen wir inkrementieren, und j wird gemäß der Einschränkung {(i + j) = k} gefunden, dh in der binären Suche nach rechts bewegen, dh make startIndex = middleIndex

    In Fall4 , um es zu Fall 1 oder Fall 2 zu formen, müssen wir dekrementieren i und j werden entsprechend der Einschränkung gefunden {(i + j) = k} dh in der binären Suche nach links verschieben, also endIndex = middleIndex .

    Now how to decide startIndex and endIndex at beginning of binary search over arr1 with startindex = 1 and endIndex = ??.We need to decide.

    If k > sz1,endIndex = (sz1+1) , else endIndex = k;

    Because if k is greater than the size of the first array we may have to do binary search over the entire array arr1 else we only need to take first k elements of it because sz1-k elements can never contribute in calculating kth smallest.

    CODE Shown Below

     // Complexity O(log(n)+log(m)) #include using namespace std; #define f(i,x,y) for(int i = (x);i < (y);++i) #define F(i,x,y) for(int i = (x);i > (y);--i) int max(int a,int b){return (a > b?a:b);} int min(int a,int b){return (a < b?a:b);} int mod(int a){return (a > 0?a:((-1)*(a)));} #define INF 1000000 int func(int *arr1,int *arr2,int sz1,int sz2,int k) { if((k < = (sz1+sz2))&&(k > 0)) { int s = 1,e,i,j; if(k > sz1)e = sz1+1; else e = k; while((es)>1) { i = (e+s)/2; j = ((k-1)-(i-1)); j++; if(j > (sz2+1)){s = i;} else if((arr1[i] >= arr2[j-1])&&(arr1[i] < = arr2[j]))return arr1[i]; else if((arr2[j] >= arr1[i-1])&&(arr2[j] < = arr1[i]))return arr2[j]; else if(arr1[i] < arr2[j-1]){s = i;} else if(arr1[i] > arr2[j]){e = i;} else {;} } i = e,j = ((k-1)-(i-1));j++; if((arr1[i] >= arr2[j-1])&&(arr1[i] < = arr2[j]))return arr1[i]; else if((arr2[j] >= arr1[i-1])&&(arr2[j] < = arr1[i]))return arr2[j]; else { i = s,j = ((k-1)-(i-1));j++; if((arr1[i] >= arr2[j-1])&&(arr1[i] < = arr2[j]))return arr1[i]; else return arr2[j]; } } else { cout << "Data Invalid" << endl; return -INF; } } int main() { int n,m,k; cin >> n >> m >> k; int arr1[n+2]; int arr2[m+2]; f(i,1,n+1) cin >> arr1[i]; f(i,1,m+1) cin >> arr2[i]; arr1[0] = -INF; arr2[0] = -INF; arr1[n+1] = +INF; arr2[m+1] = +INF; int val = func(arr1,arr2,n,m,k); if(val != -INF)cout < < val << endl; return 0; } 

    For Solution of complexity (log(n)*log(m))

    Just i missed using advantage of the fact that for each i the j can be found using constraint {(i-1)+(j-1)=(k-1)} So for each ii was further applying binary search on second array to find j such that arr2[j] < = arr1[i].So this solution can be optimized further

    Basically, via this approach you can discard k/2 elements at each step. The K will recursively change from k => k/2 => k/4 => … till it reaches 1. So, Time Complexity is O(logk)

    At k=1 , we get the lowest of the two arrays.

    The following code is in JAVA. Please note that the we are subtracting 1 (-1) in the code from the indices because Java array’s index starts from 0 and not 1, eg. k=3 is represented by the element in 2nd index of an array.

     private int kthElement(int[] arr1, int[] arr2, int k) { if (k < 1 || k > (arr1.length + arr2.length)) return -1; return helper(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k); } private int helper(int[] arr1, int low1, int high1, int[] arr2, int low2, int high2, int k) { if (low1 > high1) { return arr2[low2 + k - 1]; } else if (low2 > high2) { return arr1[low1 + k - 1]; } if (k == 1) { return Math.min(arr1[low1], arr2[low2]); } int i = Math.min(low1 + k / 2, high1 + 1); int j = Math.min(low2 + k / 2, high2 + 1); if (arr1[i - 1] > arr2[j - 1]) { return helper(arr1, low1, high1, arr2, j, high2, k - (j - low2)); } else { return helper(arr1, i, high1, arr2, low2, high2, k - (i - low1)); } } 
     #include  using namespace std; int findKthElement(int a[],int start1,int end1,int b[],int start2,int end2,int k){ if(start1 >= end1)return b[start2+k-1]; if(start2 >= end2)return a[start1+k-1]; if(k==1)return min(a[start1],b[start2]); int aMax = INT_MAX; int bMax = INT_MAX; if(start1+k/2-1 < end1) aMax = a[start1 + k/2 - 1]; if(start2+k/2-1 < end2) bMax = b[start2 + k/2 - 1]; if(aMax > bMax){ return findKthElement(a,start1,end1,b,start2+k/2,end2,kk/2); } else{ return findKthElement(a,start1 + k/2,end1,b,start2,end2,kk/2); } } int main(void){ int t; scanf("%d",&t); while(t--){ int n,m,k; cout< <"Enter the size of 1st Array"<>n; int arr[n]; cout< <"Enter the Element of 1st Array"<>arr[i]; } cout< <"Enter the size of 2nd Array"<>m; int arr1[m]; cout< <"Enter the Element of 2nd Array"<>arr1[i]; } cout< <"Enter The Value of K"; cin>>k; sort(arr,arr+n); sort(arr1,arr1+m); cout<  

    Time Complexcity is O(log(min(n,m)))

    Check this code.

     import math def findkthsmallest(): A=[1,5,10,22,30,35,75,125,150,175,200] B=[15,16,20,22,25,30,100,155,160,170] lM=0 lN=0 hM=len(A)-1 hN=len(B)-1 k=17 while True: if k==1: return min(A[lM],B[lN]) cM=hM-lM+1 cN=hN-lN+1 tmp = cM/float(cM+cN) iM=int(math.ceil(tmp*k)) iN=k-iM iM=lM+iM-1 iN=lN+iN-1 if A[iM] >= B[iN]: if iN == hN or A[iM] < B[iN+1]: return A[iM] else: k = k - (iN-lN+1) lN=iN+1 hM=iM-1 if B[iN] >= A[iM]: if iM == hM or B[iN] < A[iM+1]: return B[iN] else: k = k - (iM-lM+1) lM=iM+1 hN=iN-1 if hM < lM: return B[lN+k-1] if hN < lN: return A[lM+k-1] if __name__ == '__main__': print findkthsmallest(); 

    Below C# code to Find the k-th Smallest Element in the Union of Two Sorted Arrays. Time Complexity : O(logk)

      public static int findKthSmallestElement1(int[] A, int startA, int endA, int[] B, int startB, int endB, int k) { int n = endA - startA; int m = endB - startB; if (n < = 0) return B[startB + k - 1]; if (m <= 0) return A[startA + k - 1]; if (k == 1) return A[startA] < B[startB] ? A[startA] : B[startB]; int midA = (startA + endA) / 2; int midB = (startB + endB) / 2; if (A[midA] <= B[midB]) { if (n / 2 + m / 2 + 1 >= k) return findKthSmallestElement1(A, startA, endA, B, startB, midB, k); else return findKthSmallestElement1(A, midA + 1, endA, B, startB, endB, k - n / 2 - 1); } else { if (n / 2 + m / 2 + 1 >= k) return findKthSmallestElement1(A, startA, midA, B, startB, endB, k); else return findKthSmallestElement1(A, startA, endA, B, midB + 1, endB, k - m / 2 - 1); } }