算法基础

2.1-3

i = 1
while i ≤ n and A[i] ≠ v
  i = i + 1
// 循环结束时，要么 A[i] == v, 要么 i == n+1
if i == n + 1
  i = NIL

2.1-4

// 整数的值为 Σ A[i] * 2^i-1, 小的 i 表示低位
carry = 0
for i = 1 to n
  C[i] =  (A[i] + B[i] + carry) mod 2
  carry = A[i] + B[i] + carry > 1
C[n+1] = carry

2.2-2

for i = 1 to n-1
  min = i
  for j = i to n
    if A[j] < A[min]
      min = j
  swap(A[i], A[min])
// 最好最坏皆 Θ(n²).
// 加入
// if i > 1 and A[i] == A[i-1]
//     continue
// 以优化算法

2.3-3

`T(2) = 2 = lg(2)`. 若 `T(2^k) = k 2^k`, 则 `T(2^(k+1)) = 2k * 2^k + 2^(k+1) = (k+1)2^(k+1)`.

2.3-4

`T(n) = { Theta(1), if n = 1; T(n-1) + Theta(n), if n gt 1; :}`

2.3-5 bi-search

// precondition: array A is sorted
lo = 1
hi = A.length
mid = (lo + hi)/2
while lo ≤ hi and A[mid] ≠ v
  mid = (lo + hi)/2
    if A[mid] > v
      hi = mid
    else  // A[mid] < v
      lo = mid + 1
// not found?
if lo > hi
  mid = NIL

2.3-6

不能，因为实现新元素的插入需要移动已有元素，那需要 `Theta(n)`.