en/latest/binary-search

[utterances-bot]

Binary Search — LCtemplates documentation

https://lctemplates.xyli.codes/en/latest/binary-search.html

[mingyEx]

建议对同一个问题求其最大值和最小值，以演示”min problem是如何转换为max problem"的。 因为对于这个问题，我写了两种做法，cond1和cond2是相反的，但是无论如何我都得在最终的结果里-1. 我分不清它到底属于min problem还是max problem了。 也不知道-1到底什么时候该加什么时候不该..

441. 排列硬币 做法1：

class Solution {
  int binarySearch(long long l, long long r, int n)
  {
    while (l < r) {
      long long m = l + (r - l) / 2;
      auto sum = m * (m+ 1) / 2;
      if (sum > n)  
        r = m;
      else
         l = m + 1;
    }
    return l - 1; 
  }
public:
  int arrangeCoins(int n) {
    if (n == 1)return 1;
    int l = 1, r = n;
    return binarySearch(l, r, n);
  }
};

做法2

class Solution {
  int binarySearch(long long l, long long r, int n)
  {
    while (l < r) {
      long long m = l + (r - l) / 2;
      auto sum = m * (m+ 1) / 2;
      if (sum <= n)  
         l = m + 1;
      else
         r = m; 
    }
    return l - 1; 
  }
public:
  int arrangeCoins(int n) {
    if (n == 1)return 1;
    int l = 1, r = n;
    return binarySearch(l, r, n);
  }
};

请问这两种算不算max problem和min problem呢？ 是否就算我把原问题改为为计算并返回不可形成 完整阶梯行 的总行数，即找到最小的不可能解，才算把问题转换成了min problem,哪种情况下代码里才不需要return l-1里的-1?

[mingyEx]

也不知道-1到底什么时候该加什么时候不该..

对于这个问题我是知道的,但是，您能否更准确地定义一下max problem和min problem,以及用同一个问题来展示这两者如何转化。

我现在似乎想明白了，min problem是在范围内找到valid的最小值，所以永远return l, max problem是找到第一个invalid的值，所以永远返回l-1,是这样吗。 如何把一个问题的代码里return l-1 转换成return l的，这并不属于min <-> max相互转换的范围，而是被具体题目限定死了的，是这样吗？

[li-xin-yi]

也不知道-1到底什么时候该加什么时候不该..

对于这个问题我是知道的,但是，您能否更准确地定义一下max problem和min problem,以及用同一个问题来展示这两者如何转化。

我现在似乎想明白了，min problem是在范围内找到valid的最小值，所以永远return l, max problem是找到第一个invalid的值，所以永远返回l-1,是这样吗。 如何把一个问题的代码里return l-1 转换成return l的，这并不属于min <-> max相互转换的范围，而是被具体题目限定死了的，是这样吗？

可以这样想，跳出while循环时的left是第一个使得check条件不成立的值，如果需要的就是最小的使check不成立的值，那就直接返回left，如果需要的是最大的使check成立的值，那就return left-1。我不觉得这是被题目限定的，可以通过写不同的check函数（或者调换if语句）来转换最终跳出while时left的意义，只要你自己记得住别被绕晕就可以，这种模板哪个顺手写哪个。

[mingyEx]

嗯嗯，通过 1300. Sum of Mutated Array Closest to Target 我觉得自己已经搞懂了，顺便发现此类问题有一个通用的名字 二分查找的拓展:函数化. 昨晚搞LC2305时候被坑的挺惨，觉得以后难点都在”函数化“上了。 现在只差LC2141 就搞完练习题了

顺便，我这边好像没有close按钮，如果您觉得此问题应该标记为已解决的话就关掉吧