请教一道lintcode上的题：wood cut

Description
Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

The unit of length is centimeter.The length of the woods are all positive integers,you couldn't cut wood into float length.If you couldn't get >= k pieces, return 0.

Example 1
Input:
L = [232, 124, 456]
k = 7
Output: 114
Explanation: We can cut it into 7 pieces if any piece is 114cm long, however we can't cut it into 7 pieces if any piece is 115cm long.

LC上有很多类似的题，对于这道题，思路也是类似的，用二分法来trial and error。
主要问题是这个二分搜索的结束条件 while (lo + 1 < hi) { // why lo+1 < hi？
通过跑例子，我能知道应该用这个条件，否则无法exit loop。
但是一开始想的时候怎么想到呢？请大神们赐教～

1. public class Solution {
   
2.     /**
   
3.      * @param L: Given n pieces of wood with length L[i]
   
4.      * @param k: An integer
   
5.      * @return: The maximum length of the small pieces
   
6.      */
   
7.     public int woodCut(int[] L, int k) {
   
8.         // write your code here
   
9.         int lo = 1, hi = 0;
   
10.         for (int l : L) {
    
11.             hi = Math.max(l, hi);
    
12.         }
    
13.         while (lo + 1 < hi) {   // why lo+1 < hi？
    
14.             int mid = lo + (hi-lo)/2;
    
15.             int numPieces = getNumPieces(L, mid);
    
16.             if (numPieces >= k) {
    
17.                 lo = mid;  // lo is a possible candidate, so lo = mid (not mid+1)
    
18.             } else {
    
19.                 hi = mid - 1;
    
20.             }
    
21.         }
    
22.         if (getNumPieces(L, hi) >= k) return hi;
    
23.         if (getNumPieces(L, lo) >= k) return lo;
    
24.         return 0;
    
25.     }
    
26. 
    
27.     private int getNumPieces(int[] L, int len) {
    
28.         int ans = 0;
    
29.         for (int l : L) {
    
30.             ans += l / len;
    
31.         }
    
32.         return ans;
    
33.     }
    
34. }

复制代码

主要是经验，注意二分的形式：

如果是 lo = mid, hi = mid - 1显然是没法跳出循环的，需要特殊判断差为1的情况
如果是 lo = mid + 1, hi = mid 是没问题的

但前者推荐你这么写：int mid = lo + ((hi-lo+1)>>1);
这样如果是差1会被assign成hi，就不存在这个问题了

二分其实应用了单调性，也就是说如果一个长度可以切出那么多来，那比他小的长度一定都可以。如果一个长度切不出来，那么比他大的也一定切不出来。这样的话就可以求两个的边界点，也就是可以用二分。类似first bad ver sion

换做我会这么写：
```
public class Solution {
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        int lo = 1, hi = 0;
        for (int l : L) {
            hi = Math.max(l, hi);
        }
        while (lo < hi) {  
            int mid = hi - (hi-lo)/2;
            int numPieces = getNumPieces(L, mid);
            if (numPieces >= k) {
                lo = mid;  // lo is a possible candidate, so lo = mid (not mid+1)
            } else {
                hi = mid - 1;
            }
        }
        return hi;
    }
}
```
注意两点：
1. 模板永远用while (lo<hi)，这样退出循环的时候一定是lo==hi. 因为本题一定有合理解，所以收敛解就是最终的最优解，不需要额外check答案。
2. 根据hi/lo来算mid这一行会需要根据你后面的代码做变动。本题中 ```... lo=mid; ... hi = mid - 1... ```为了避免死循环，所以你就需要写成mid = hi-(hi-lo)/2。 如果在其他题目里是 ```... lo = mid+1; ... hi = mid...``` 那么你就要写成mid = lo+(hi-lo)/2. 这个不需要死记硬背，你想想lo=0,hi=1，那么下一轮为了防止继续lo=0,hi=1，你该怎么写。

cnxhk 发表于 2021-4-23 03:35
主要是经验，注意二分的形式：

如果是 lo = mid, hi = mid - 1显然是没法跳出循环的，需要特殊判断差为1 ...

多谢指点！
想给大佬加米，但是积分不够，加不成。。

补充内容 (2021-04-25 00:22 +8:00):
我的积分到100了，可以给各位加米了

直接写成l+1<r
l=mid
r=mid
最后出来l和r再判断一下
这样就不用纠结会不会死循环了
这种二分对新手友好
九章算法学来的哈哈

wisdompeak2 发表于 2021-4-23 11:15
换做我会这么写：
```
public class Solution {

多谢大佬指点！有些特别tricky的test case，我加了一个判断if (sum < k) return 0; 这样就可以把binary search之后的那些判断删去了。

1.     public int woodCut(int[] L, int k) {
   
2.         if (L == null || L.length == 0)
   
3.             return 0;
   
4.         // System.out.println("L length = " + L.length + ", k = " + k);
   
5.         // write your code here
   
6.         int lo = 1, hi = 0;
   
7.         long sum = 0;
   
8.         for (int l : L) {
   
9.             hi = Math.max(l, hi);
   
10.             sum += l;
    
11.         }
    
12.         if (sum < k) return 0;
    
13.         while (lo < hi) {  
    
14.             // int mid = lo + (hi-lo+1)/2;
    
15.             int mid = hi - (hi-lo)/2;
    
16.             int numPieces = getNumPieces(L, mid);
    
17.             if (numPieces >= k) {
    
18.                 lo = mid;  // lo is a possible candidate, so lo = mid (not mid+1)
    
19.             } else {
    
20.                 hi = mid - 1;
    
21.             }
    
22.         }
    
23.         // if (getNumPieces(L,hi) >= k) return hi;
    
24.         // if (getNumPieces(L,lo) >= k) return lo;
    
25.         return lo;
    
26.     }

复制代码

具体请看我的帖子https://www.1point3acres.com/bbs/thread-747061-1-1.html
我觉得非常清楚了

pxuu 发表于 2021-4-24 08:00
多谢大佬指点！有些特别tricky的test case，我加了一个判断if (sum < k) return 0; 这样就可以把binary s ...

具体请看我的帖子https://www.1point3acres.com/bbs/thread-747061-1-1.html
我觉得非常清楚了，请仔细阅读，多谢

在这里我要指出来，你最好写成一个返回boolean的函数，为什么？因为可以提前退出。

二分答案即可