Java算法（递归）：两个不同长度的有序数组求第k小的元素（时间复杂度为：O(log(m1 + m2))）。

首先看到时间复杂度要求就可以确定使用折半查找的思想。由于数组下标是从0开始计数，我们可以将k也定义为从0开始，那么原本题目中的第k小（k从1开始），在我们算法中就表示成第k-1小（k从0开始）。

注意每次取mid1和mid2时，都应该考虑有没有越界情况的发生。

public class ex_2 {public static void main(String[] args) {int[] arr1 = new int[]{1, 2, 3};int[] arr2 = new int[]{0, 4, 5, 6, 7, 8};System.out.println(findKth(arr1, arr2, 2));}public static int findKth(int[] arr1, int[] arr2, int k) {if (arr1 == null || arr1.length < 1) {return arr2[k - 1];}if (arr2 == null || arr2.length < 1) {return arr1[k - 1];}return findKth(arr1, 0, arr1.length - 1, arr2, 0, arr2.length - 1, k - 1);}public static int findKth(int[] arr1, int l1, int r1, int[] arr2, int l2, int r2, int k) {if (l1 > r1) {return arr2[l2 + k];}if (l2 > r2) {return arr1[l1 + k];}if (k == 0) {return Math.min(arr1[l1], arr2[l2]);}int mid1 = l1 + k / 2 < r1 ? l1 + k / 2 : r1;int mid2 = l2 + k / 2 < r2 ? l2 + k / 2 : r2;if (arr1[mid1] < arr2[mid2]) {return findKth(arr1, mid1 + 1, r1, arr2, l2, r2, k - (k / 2) - 1);} else if (arr1[mid1] > arr2[mid2]) {return findKth(arr1, l1, r1, arr2, mid2 + 1, r2, k - (k / 2) - 1);} else {return arr2[mid2];}}}