#! /usr/bin/gawk -f
# Last edited on 2004-04-26 19:40:51 by stolfi

BEGIN {
  # Define data
  #            01  02  03  04  05  06  07  08  09  10
  n1 = split("200 190 180 150 140 120 110 100 050 010", a);
  n2 = split("170 160 130 090 080 070 060 040 030 020", b);
  if (n1 != n2) { error("unequal vecs"); }
  n = n1;
  
  # Find {i} and {j = n-i} such that the {n} largest 
  # elements are {a[1..i]} and {b[1..j]}.
  imin = 0;
  imax = n;
  while (imin < imax)
    { printf "range is a[%02d..%02d] b[%02d..%02d]:", \
        imin, imax, n-imax, n-imin;
      i = int((imin+imax)/2); j = n-i;
      printf "  testing a[%02d] against b[%02d]...\n", i, j;
      if ((i < n) && (j > 0) && (a[i+1] > b[j]))
        { imin = i+1; }
      else if ((i > 0) && (j < n) && (a[i] < b[j+1]))
        { imax = i-1; }
      else
        { imin = i; imax = i; }
    }
  i = imin; j = n-i;
  printf "the first %d elems are", n;
  printf " a[01..%02d] merged with b[01..%02d]\n", i, j;
  
  # Decide which was the last merged element, {a[i]} or {b[j]}.
  if (i == 0)
    { which = "b"; pos = j; val = b[j]; }
  else if (j == 0)
    { which = "a"; pos = i; val = a[i]; }
  else if (a[i] < b[j])
    { which = "a"; pos = i; val = a[i]; }
  else
    { which = "b"; pos = j; val = b[j]; }
  printf "median is %s[%02d] = %s\n", which, pos, val;
}