LeetCode题解：1237. 找出给定方程的正整数解，二分查找，详细注释

原题链接： leetcode.cn/problems/fi…

解题思路：

1. 根据题意，在给定x的情况下，y是单调递增的
2. 因此，我们可以从1到1000枚举x，就可以在固定x的情况下，用二分查找搜索y的值
3. 如何二分查找：
   • 首先声明左边界let yLeft = 1，右边界let yRight = 1000
   • 计算它们的中间值，const yMiddle = (yLeft + yRight) >> 1，或者可以用const yMiddle = Math.floor((yLeft + yRight) / 2)
   • 如果中间值用函数计算的结果customfunction.f(x, yMiddle)大于z，说明y的值在yLeft和yMiddle之间，因此可以让yRight = yMiddle - 1，继续在yLeft和yMiddle - 1之间查找y
   • 如果中间值用函数计算的结果customfunction.f(x, yMiddle)小于z，说明y的值在yMiddle和yRight之间，因此可以让yLeft = yMiddle + 1，继续在yRight和yMiddle + 1之间查找y

/**
 * @param {CustomFunction} customfunction
 * @param {integer} z
 * @return {integer[][]}
 */
var findSolution = function(customfunction, z) {
  let result = [] // 存储结果

  // 枚举所有x
  for (let x = 1; x <= 1000; x++) {
    let yLeft = 1 // 二分查找的左边界
    let yRight = 1000 // 二分查找的右边界

    // 在固定x的前提下，二分查找y的值
    while (yLeft <= yRight) {
      // 取左右边界的中间值
      const yMiddle = (yLeft + yRight) >> 1
      // 用函数计算中间值的结果
      const middleResult = customfunction.f(x, yMiddle)

      // 如果结果等于z，这时找到的x和y是是解之一
      if (middleResult === z) {
        result.push([x, yMiddle])
      }

      // 如果结果大于z，说明y的值在yLeft和yMiddle之间，因此将右边界移动到yMiddle - 1
      if (middleResult > z) {
        yRight = yMiddle - 1
      } else {
        // 如果结果小于z，说明y的值在yMiddle喝yRight之间，因此将左边界移动到yMiddle - 1
        yLeft = yMiddle + 1
      }
    }
  }

  return result
};

复杂度分析：

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(1)$。返回值不计入空间复杂度