BS on result

Find maximum or minimum

No list, find result based on binary search

69 Sqrt(x)

• Similar code, but if (mid < x/mid)

• Jump out the loop. if (end*end <= x) return end

public int mySqrt(int x) {
    if(x == 0) return 0;
    int start = 0, end = x;

    while(start+1<end){
        int mid = start + (end-start)/2;
        if(mid == x/mid) return mid; // mid移項避免int越界
        else if(mid > x/mid) end = mid;
        else start = mid;
    }
    if(end <= x/end) return end;
    return start;
}

First bad version

Given a boolean function isBadVersion

public int findFirstBadVersion(int n) {
    // write your code here
    long start = 1, end = n;
    while(start + 1 < end){
        long mid = (start + end) / 2;
        if(SVNRepo.isBadVersion((int)mid)){
            end = mid;
        }else{
            start = mid;
        }
    }

    // 2 case [false, true], [true, true]
    if(SVNRepo.isBadVersion((int)start)){
        return (int) start;
    }else{
        return (int) end;
    }
}

Wood cut

Given an integer array representing different length of wood. Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length

• create function to count the piece sum of L

• if count >= k, means k is small, set start = mid

public int woodCut(int[] L, int k) {
    // find the longest wood
    int max = 0;
    for (int i = 0; i < L.length; i++){
        max = Math.max(L[i], max);
    }

    int start = 1, end = max;

    while(start + 1 < end){
        int mid = start + (end-start)/2;
        if (count(L, mid) >= k){
            start = mid;
        }else{
            end = mid;
        }
    }

    if(count(L, start) >= k){
        return start;
    }
    if(count(L, end) >= k){
        return end;
    }
    return 0;
}

    // count the total pieces of wood length L

private int count(int[] L, int len){
    int piece = 0;
    for (int i = 0; i < L.length; i++){
        piece += (int)L[i]/len;
    }

    return piece;
}