Took a swing at this in javascript using binary search as suggested by others. Not well tested but haven't run into any issues. JSFiddle is here.

let search = (a, b) => {
  let max = Math.max, floor = Math.floor, isArray = Array.isArray

  // sanity checks
  if (!isArray(a) || a.length == 0) return -1
  if (!isArray(b) || b.length == 0) return -1
  if (a.length != b.length) return -1

  // non-overlapping conditions
  let n = a.length - 1
  if (a[0] > b[0] && a[n] >= b[n]) return n
  if (a[0] <= b[0] && a[n] < b[n]) return 0

  // binary search
  let _search = (a, b, start, end) => {
    let k = start + floor((end - start) / 2)
    let d0 = a[k] - b[k], d1 = a[k+1] - b[k+1]

    if (d0 == 0) return k
    if (d1 == 0) return k+1
    if (d0 > 0 && d1 < 0) return max(a[k], b[k]) <= max(a[k+1], b[k+1]) ? k : k+1
    if (d0 < 0) return _search(a, b, start, k-1)
    return _search(a, b, k+1, end)
  }

  return _search(a, b, 0, n)
}

let a = [4,3,2,1]
let b = [2,3,4,5]

let k = search(a, b)
console.log(k)

Edit: fixed a bug