leetcode二分法合集

就是为了干倒二分题目。

题目

475. Heaters

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters‘ warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.
 

Example 1:

Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
 

Example 2:

Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

1.  将房屋和暖气的位置分别从小到大排序。
2.  假设得到了加热半径 r，即可在O(n+m)的时间内，判断是否所有的房屋都得到了暖气，具体为，逐一枚举房屋，然后判断是否有暖气覆盖，由于房屋和暖气的坐标都是单调的，所以第i+1个房屋不会使用坐标小于第i个房屋的暖气位置。
3.  加热半径也是单调的，故可以使用二分来加速寻找最小的半径。

import java.util.*;

class Main {
    //定义域：半径长度
    //值域：给房所有房子供暖
    //最优解：可以给房子供暖的半径中求一条最短的。upper_bound
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        Arrays.sort(houses);
        if (houses.length==0)
            return 0;
        int l=0;
        int r=Math.max(houses[houses.length-1],heaters[heaters.length-1]);
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid,houses,heaters)) r = mid;//半径长度太长
            else l = mid + 1;//半径长度太短
        }
        return l;
    }
    boolean check(int r,int[] houses, int[] heaters){
        int n = heaters.length;
        for (int i = 0, j = 0; i < houses.length; i++) {
            while (j < n && Math.abs(houses[i] - heaters[j]) > r)
                j++;
            if (j == n)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
    }
}

题目

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
  the decimal part is truncated, 2 is returned.

定义域：输入x

值域：x的开方

最优解：开发根的向下取整数low_bound

class Solution {
    public int mySqrt(int x) {
        return bsearch_2(0, x, x);
    }

    int bsearch_2(int l, int r, int x) {
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
}

leetcode二分法合集

原文：https://www.cnblogs.com/clarencezzh/p/11048408.html