那些你想不到的二分查找.md

二分查找的基本用法已经总结过，在二分查找基础篇中总结过。二分查找在于判断条件以及排除绝对不可能存在的区间。

这篇文章会总结一些不是那么直观的二分查找的应用的题目。

题目：一个数轴上有n个超市，用数字表示超市的位置。小明要去m个超市，请问小明能去的所有m个超市，相邻超市的距离的最小值之中的最大值是多少。 例子，超市位置 1 2 4 8 9。小明要去三个超市，所选的三个超市中相邻超市距离最小的值的最大值为3。当选择为1 4 9或者1 4 8的时候。

分析： 这道题一开始的思路是暴力的方法，选出所有的组合，分别求最小值，然后再求所有组合中的最大值。这显然是会超出时间限制的。 关键在于分析这道题目是求一个最大值，即符合条件的最大值，看起来是单调递增的，所有取值都是有可能。因此这道题可以用二分查找的思想来做。

超市距离：1 2 4 8 9 
由于不可能重复，因此距离的最小值是1，最大值是8。这两个值取大一点也无所谓，因为会通过判断比较是否存在满足要求的选择。
left=1, right=8, mid = (1+8)/2=4
因此需要是否存在最小值为4的选择。
遍历1 2 4 8 9，用一个值pre表示前一个位置，用一个值cnt表示已经选中的个数。从第二个开始遍历，下一个减上一个位置距离大于mid，cnt++。
i=1，pre=1，cnt=0，a[i]-pre<mid，不成立。
i=2，pre=1，cnt=0，a[i]-pre<mid。
i=3，pre=1，cnt=0，a[i]-pre>=mid，更新pre=8，cnt++。
i=4，pre=8，cnt=1，a[i]-pre<mid，不成立。
当cnt没达到要求的选择的数时，返回false，否则直接返回true。
因为求的是最大值，当mid不满足条件时，则说明比mid大的更加不可能。当mid满足条件时，探索比mid大的值。

#include <bits/stdc++.h> 
using namespace std; 
bool isFeasible(int mid, int arr[], int n, int k) 
{ 
    int pos = arr[0]; 
    int elements = 1; 
    for (int i=1; i<n; i++) 
    { 
        if (arr[i] - pos >= mid) 
        { 
            pos = arr[i]; 
            elements++; 
            if (elements == k) 
              return true; 
        } 
    } 
    return 0; 
} 
int largestMinDist(int arr[], int n, int k) 
{ 
    sort(arr,arr+n); 
    int res = -1; 
    int left = arr[0], right = arr[n-1]; 
    while (left < right) 
    { 
        int mid = (left + right)/2; 
        if (isFeasible(mid, arr, n, k)) 
        { 
            res = max(res, mid); 
            left = mid + 1; 
        } 
        else
            right = mid; 
    } 
    return res; 
} 
// Driver code 
int main() 
{ 
    int arr[] = {1, 2, 8, 4, 9}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int k = 3; 
    cout << largestMinDist(arr, n, k); 
    return 0; 
}