問題：100個運動員站成兩排，每排已經(jīng)按從高到低順序排好，教練想找出身高排40位的隊員舔亭，請問最少需要幾次比較脖律？（限制每次只能兩個隊員比身高）
分析: 也就是從兩個有序數(shù)組中谢肾，找第k大的值。歸并比較的話需要O(k)小泉，所以這題希望找復(fù)雜更小的答案芦疏，比如O(logK)之類的。寫個test先:

describe KthOfTwoSorted do
  let(:result) {subject.kth_of_two_sorted(n-1,x,y)}
  context "simple example" do
    let(:x) {[1,3,5,7,9]}
    let(:y) {[2,4,6,8,10]}
    let(:n) {8}
    let(:ans) {8}
    it "should find kth" do
      expect(result).to eq ans
    end
  end

make hands dirty

分析: 要小于O(k), 就不能訪問所有元素微姊，某些元素沒被訪問就可以排除了酸茴。

從第一隊取出第15個人A，第2隊取出第25個人B兢交，如果A<B薪捍，可以發(fā)現(xiàn)包括第一隊包括A在內(nèi)的這15人都可以排除了（想想為什么）。
因此配喳，我們每次從第一組取第k/2個酪穿，第二組第k-k/2個，這樣一次比較就能排除一半的人晴裹，yes!

coding

于是昆稿，try偽碼:

def kth(k, arrx, arry)
    return [arrx.first, arry.first].min if k==0

    xmid = k/2
    ymid = k-xmid
    if arrx[xmid] <= arry[ymid]
      kth(k-xmid-1, arrx[xmid+1..-1], arry)
    else
      kth(k-ymid-1, arrx, arry[ymid+1..-1])
    end
  end

擴充完整：

class KthOfTwoSorted
  def safe_kth(k, arrx, arry)
    return [arrx.first,arry.first].compact.min if k==0

    xmid = k/2
    ymid = k-(xmid+1)
    if arrx[xmid] <= arry[ymid]
      safe_kth(k-xmid-1, shift(arrx,xmid+1), arry)
    else
      safe_kth(k-ymid-1, arrx, shift(arry, ymid+1))
    end
  end

  def kth_of_two_sorted(k, arrx, arry)
    (arrx.size+arry.size).tap do |len|
      raise ArgumentError,"k should in range #{0..len}" unless 0<=k && k<len
    end

    arrx,arry = [arrx,arry].sort_by(&:size)
    if arrx.size < k
      arry.shift(k-arrx.size)
      k = arrx.size
    end

    safe_kth(k, arrx, arry)
  end

  private
  def shift(arr, n); arr.shift(n);arr end
end

測試代碼:

require_relative '../kth_of_two_sorted_list'

shared_examples_for "find kth" do
  it "should find kth" do
    # k = n-1
    # ans = (x+y).sort[k]
    expect(result).to eq ans
  end
end

describe KthOfTwoSorted do
  let(:result) {subject.kth_of_two_sorted(n-1,x,y)}
  context "example normal" do
    let(:x) {[1,3,5,7,9]}
    let(:y) {[2,4,6,8,10]}
    let(:n) {8}
    let(:ans) {8}
    it_behaves_like "find kth"
  end
  context "when one is empty" do
    let(:x) {[]}
    let(:y) {(1..10).to_a}
    let(:n) {9}
    let(:ans) {9}
    it_behaves_like "find kth"
  end
  context "when one is too short" do
    let(:x) {[1,2,3]}
    let(:y) {(4..10).to_a}
    let(:n) {9}
    let(:ans) {9}
    it_behaves_like "find kth"
  end
  context "when repeat" do
    let(:x) {(1..100).select(&:odd?) + (101..200).to_a}
    let(:y) {(1..100).select(&:even?) + (101..200).to_a}
    let(:n) {200}
    let(:ans) {150}
    it_behaves_like "find kth"
  end
  context "when out of range" do
    let(:x) {[]}
    let(:y) {x}
    let(:n) {10}
    it "should raise error" do
      expect{result}.to raise_error(/k should in range/)
    end
  end
end