二分搜索、最大子序列伪代码

最大子序列

  • 前i个元素中,最大子序列要么在前i-1个元素中(存储在maxsofar中),要么其结束位置为i(存储在maxendinghere中)。
  • 最后结果存储在maxsofar中,但是需要着重理解maxendinghere
    maxsofar = 0
    maxendinghere = 0
    for i = [0, n)
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)
    end

二分搜索

二分搜索1

  • 最简单的二分搜索,但是对于连续的t,无法保证顺序
    l = 0; u = n-1
    loop
    if l > u
    p = -1; break
    end
    m = (l + u)/2
    case
    x[m] < t: l = m+1
    x[m] == t: p = m; break
    x[m] > t: u = m-1
    end
    end

二分搜索2

  • 可以确定t在数组中第一次出现的位置
  • 循环中只进行一次比较,更加高效
    l = -1; u = n
    while l+1 != u
    m = (l + u)/2
    if x[m] < t
    l = m
    else
    u = m
    end
    end
    p = u
    if p >= n || x[p] != t
    p = -1
    end

生成m个随机数

  • bigrand() 返回一个远大于n或者m的随机数
    for i = [0, n)
    // select m of remaining n-i
    if (bigrand() % (n-i)) < m
    print i
    m--
    end
    end