面试题：从有序数组中找到两个数最佳匹配和

试题：从类型为Array<Number>的有序数组中，找出两个数 x 和 y，使得 xy 之和无限接近一个指定的数 n，实现函数 find(arr, n) ，返回找到的两个数 x的y 并使其 x + y <= n

var arr = [-6.3, -4.33, -3.5, -1.5, 0.33, 5, 6.5, 8.2, 13.4]

var c = find(arr, 5)

if (c === -1) {
    console.log('不存在')
} else {
    console.log(c.join())
}

function find(arr, n) {
    var nIndex = binaryInsertion(arr, n)
    var inArr = false

    // 找到完全匹配项
    if (arr[nIndex] === n) {
        var zeroIndex = binaryInsertion(arr, 0)
        var zero = arr[zeroIndex]
        inArr = true

        if (!zero) {
            return n > 0 ? [0, arr[nIndex]] : [arr[nIndex], 0]
        }
    }

    // 最小项都大于n or 两最小值大于n
    if (nIndex === 0 && arr[0] + arr[1] > n) {
        return -1
    }

    // 最大两个数之和小于n
    if (nIndex === arr.length && arr[nIndex - 1] + arr[nIndex - 2] < n) {
        return [arr[nIndex - 2], arr[nIndex - 1]]
    }

    // 值一定是分布在两侧边的
    var x, y, sumX, sumY
    var sum = -99999999

    x = nIndex
    inArr && x--
    
    if (inArr && !x) return -1

    while (sum < n) {
        y = x + 1
        while (arr[x] + arr[y] <= n && arr[x] + arr[y] > sum) {
            sum = arr[x] + arr[y]
            sumX = x
            sumY = y
            y++
        }
        if (sum === n) {
            return [arr[x], arr[y - 1]]
        }
        if (x === 0) {
          break
        } else {
            x--
        }
    }

    return [arr[sumX], arr[sumY]]
}

function binaryInsertion(arr, find) {
  if (arr.length === 1) {
    return arr[0] < find ? 1 : 0
  }

  var mid = Math.floor(arr.length / 2)

  if (find < arr[mid]) {
    return binaryInsertion(arr.slice(0, mid), find)
  }
  return mid + binaryInsertion(arr.slice(mid), find)
}