2019-10-11 Daily Report

概览

春岸绿时连梦泽,夕波红处近长安。

时间:Friday, October 11, 2019 09:30 AM

作者:Syncher Pylon


  • 处理邮件
  • 更新 Todo List
  • 学习算法
  • 学习英语

算法学习笔记

今天重新审视了二分法,结合同事的思考认为,

二分的本质是,在一段或多段单调序列里找分界点

使用左开右闭 [l, r) 的模板如下:

1
2
3
4
5
6
7
8
9
def binary_search(l, r):
while l < r:
m = l + (r - l) // 2
if f(m): return m # optional
if g(m):
r = m # new range [l, m)
else:
l = m + 1 # new range [m+1, r)
return l # or not found

m 如果满足查找条件,即 f(m) 返回 true,则查找结束。如果 f(m) 返回 false, 则根据 g(m) 的结果构造新的查找区间。如果新区间在左边,则新的左闭右开区间是 [l, m) 等价于 [l, m-1];如果新区间在右边,则新的左闭右开是 [m+1, r)

Return the lower_bound / upper_bound of a value x in a sorted array.

lower_bound(A, x): first index of i, such that A[i] >= x

1
2
3
4
5
6
7
8
def lower_bound(A, x, l, r):
while l < r:
m = (l + r) // 2
if A[m] >= x:
r = m
else:
l = m + 1
return l

upper_bound(A, x): first index of i, such that A[i] > x

1
2
3
4
5
6
7
8
def upper_bound(A, x, l, r):
while l < r:
m = (l + r) // 2
if A[m] > x:
r = m
else:
l = m + 1
return l

练习:

https://leetcode.com/problems/first-bad-version/

https://leetcode.com/problems/sqrtx/

https://leetcode.com/problems/koko-eating-bananas/

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

英语学习笔记

  • Academy: [əˈkædəmi]

  • Silicon Valley: 硅谷

  • San Ramon, California

  • be crucial for

    She is crucial for you in bolding with your project team.

  • cohort: a group of people banded together or treated as a group.

  • Brazil: 巴西

  • eligible: [ˈɛlədʒəb(ə)l]

    having the right to do or obtain something; satisfying the appropriate conditions.

  • warranty: a written guarantee, issued to the purchaser of an articel by its manufacturer.

    out of warranty

本文标题:2019-10-11 Daily Report

文章作者:Syncher

发布时间:2019年10月11日 - 09:10

最后更新:2019年11月11日 - 23:11

原始链接:https://0x400.com/2019-10-11-diary-2019-10-11.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。