> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/binary_search/bs-on-result.md).

# 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`

```java
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`

```java
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`&#x20;

```java
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;
}
```