Leetcode: 69, 410, 363, 378

二分法精髓

  • 函数的单调性 + 计算内容重复

猜+判定

  • 猜答案，根据判定结果修正答案

解题流程

  • 判定答案的范围，L、R 再来猜答案
  • 找到单调关系
  • 定义guess函数，来判断猜的答案与

  • 根据guess的判定来划分区间

    注意点

  • mid = (L+R)/2, 在进行加法运算时会超过int范围

  • 区间问题：
    • 左闭右开[L, R)：mid = (L+R)/2，区间划分的时候去除掉mid,L = mid+1; R = mid;
    • 左闭右闭[L, R]：mid = (L+R)/2，区间划分的时候去除掉mid,L = mid+1; R = mid-1;
  • 循环结束条件：左闭右开[L, R) L<R; 左闭右闭[L, R] L<= R
  • 无论那种区间，要对ans进行判断，考虑target 不在 数组中的情况

分割区间

[st, mid-1] mid [mid+1, ed] 运行条件st<=ed
[st, mid) mid [mid+1, ed) 运行条件st<ed

避免整形int溢出

  • 转long
  • 改 int mid = (L + R) / 2 —-> int mid = L + (R-L)/2 —-> int mid = (L + R)/2 >>> 1

LeetCode-69

实现 int sqrt(int x) 函数。
思路：

左闭右开[L, R)**

  1. class Solution { 
  2.     public boolean guess(long x, long y) {
  3.         return (long)x * x <= y;
  4.     }
  5.     // 二分法
  6.     public int mySqrt(int y) {
  7.         // 初始化区间
  8.         long L = 0, R = (long)y + 1;
  9.         // 保留整数，所以一般来说x*x <= y
  10.         long ans = 0;
  11.         while(L < R) {
  12.             long mid = (L + R) / 2;
  13.             if(guess(mid, y)) {
  14.                 ans = mid;
  15.                 L = mid + 1;
  16.             } else {
  17.                 R = mid;
  18.             }
  19.         }
  20.         return (int) ans;
  21.     }
  22. }

左闭右闭[L, R]

class Solution { 
    public boolean guess(long x, long y) {
        return (long)x * x <= y;
    }
    // 二分法
    public int mySqrt(int y) {
        // 初始化区间
        long L = 0, R = (long)y;
        // 保留整数，所以一般来说x*x <= y
        long ans = 0;
        while(L <= R) {
            long mid = (L + R) / 2;
            if(guess(mid, y)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid-1;
            }
        }
        return (int) ans;
    }
}

LeetCode 4 寻找两个正序数组的中位数

  • 转化为求解第k大的数
    • 当总长度len为奇数时，求解k=len/2+1大的数
    • 当总长度len为偶数时，求解k=len/2+1大的数 和 k = len/2大数的 平均值
  • 举例

nums1 = [1, 3]
nums2 = [2]
len = 3，要找第k = 1 + 1大的数

  • nums1 pivot1 = 1, nums2 pivot2 = 2， 选择pivot1，计数0-0+1—> 再nums1= [3] nums2 = [2] 中找第0大的
  • 此时 k = 1， 选择nums1 nums2中位数较小的一个