二分

• 一段可化为线性的区间，且区间的某种性质也应该是线性的，这样可以得出一个点，让两侧的区间拥有不同的性质
• 这里，读入一个目标值，选取的性质是与目标值的>=<关系。这样，区间能被二分为{<=,>}或者{<,>=}，因为只有两个子区间
• 目标值可以以区间的边界语言表示，如对第一种可表示为{<=}区间右边第一个数或者{>}区间左边的第一个数。
• 为了得到边界，区间应该被不断缩小，直到只有一个或者两个点情况。
• 比如说，想要得到{<=}左边第一个数，那么二分就是{<=,>}情况。
  • 初始区间应该包含边界点或者说包含不同性质的元素。选取0~n-1就好了(i,j)
  • 然后，维护两个端点的性质，i要是第一个区间，j是第二个区间，每次取区间中点(这里先不考虑是上中点还是下中点)，相应更新边界，使边界在一般情况下保持性质(可以考虑以一个无穷长的数组)
  • 但是，因为要能跳出特殊情况（只有两个元素时），所以必定边界在更新时需要进行一些变动。在一般情况下，变动不影响边界性质，但是特殊情况时，会改变对应性质。
  • 举例： {<,>=}求=的边界，这里表示数的范围的开始，那么要维护的应该是j严格保持>=性质，i可以发生变化，变成m+1(m是中点)，对应就是下界更新时+1情形，所以要取下中点，m=i+j>>1。
  • 最后，相等时就可以取j作为返回值了，因为j严格在>=的区间内，并且跳出循环（这是由于i的改变,但是i不严格保证坐落于<区间，边界条件就是跳出循环的前一次）后区间肯定只有一个元素，这个肯定是在>=的，并且是由一个<只+1一次得来的。