二分查找你带我走吧

2517. 礼盒的最大甜蜜度

给你一个正整数数组 price ，其中 price[i] 表示第 i 类糖果的价格，另给你一个正整数 k 。

商店组合 k 类 不同 糖果打包成礼盒出售。礼盒的 甜蜜度 是礼盒中任意两种糖果 价格 绝对差的最小值。

返回礼盒的 最大 甜蜜度。

先来个错误示范：

我的思路第一步就错了，我直接当成子序列问题，但其实没必要。比如一个礼盒：

[5,3,2,4,9]

求礼盒的甜蜜度，不需要把所有的元素两两组合，只需要先排序，变成：

[2,3,4,5,9]

那么对于2这个元素，与3组合就是2的所有组合中的最小值，后面所有的组合值都更大，可以直接无视。

为什么可以这样？因为所有元素都是正整数，换言之具有单调性。

这里反映出我的思考方式还是太容易钻死胡同，也没有用分治法，先思考怎么求礼盒的甜蜜度，再求最终问题的答案，而是直接一股脑莽了进去。

我最终得到的思路是这样的:

我可以从price中减去元素，最终得到我要的那个包含最大甜蜜度的礼盒。

给price排序，从price里面减去甜蜜度最小的组合的其中一个元素，让甜蜜度变大。我能保证每一次操作都是最优的，同时最终我要的那个礼盒一定可以通过这样的减操作得到，所以我可以用这种方法得到答案。

实际上根本不行。因为这个减操作的顺序会影响最终的结果，我不知道最终的礼盒是用什么顺序执行减操作得到的，换言之局部最优解不一定是全局最优解，我得枚举全部的顺序。

分析完错误原因，来看正确答案：二分查找。

然后我在想：二分的本质就是一个值跟一组区间的关系吧，随着这个值的增大或减小，区间的数量跟大小也会增加或减少。

一个题目，只要能找到这样的关系，就可以用二分。

待续：