<?php
class Solution {

	/**
	 * @param Integer[] $nums1
	 * @param Integer[] $nums2
	 * @return Float
	 */
	function findMedianSortedArrays($nums1, $nums2) {
		$l1 = count($nums1);
		$l2 = count($nums2);

		$l = $l1 + $l2;
		if ($l % 2 == 1) {
			$ans = $this->getKthElm($nums1, $nums2, intdiv($l+1, 2));
		} else {
			$ansL = $this->getKthElm($nums1, $nums2, intdiv($l, 2));
			$ansR = $this->getKthElm($nums1, $nums2, intdiv($l, 2) + 1);
			$ans = ($ansL + $ansR) / 2.0;
		}
		return $ans;
	}

	/**
	 * 获取两个数组中，排第k位的元素，使用二分法
	 * @param $nums1
	 * @param $nums2
	 * @param $k
	 */
	function getKthElm($nums1, $nums2, $k) {
		$idx1 = 0;
		$idx2 = 0;
		$l1 = count($nums1);
		$l2 = count($nums2);

		while (true) {
			// 边界情况
			if ($idx1 == $l1) {
				return $nums2[$idx2 + $k -1];
			}
			if ($idx2 == $l2) {
				return $nums1[$idx1 + $k - 1];
			}

			if ($k == 1) {
				return min($nums1[$idx1], $nums2[$idx2]);
			}

			// 正常情况
			$half = intdiv($k, 2);
			$newIdx1 = min($idx1+$half, $l1) - 1;
			$newIdx2 = min($idx2+$half, $l2) - 1;
			if($nums1[$newIdx1] <= $nums2[$newIdx2]) {
				$k = $k - ($newIdx1 - $idx1 + 1);
				$idx1 = $newIdx1 + 1;
			} else {
				$k = $k - ($newIdx2 - $idx2 + 1);
				$idx2 = $newIdx2 + 1;
			}
		}
	}
}