算法设计与分析笔记0x05 —— 分治法(1)

Divide and Conquer

  • Break up problem into several parts
  • Solve each part recursively
  • Combine solution to sub-problems into over solution

Let’s consider about mergesort.
$$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + n$$
We solve it and get T(n)=O(nlogn), which could be proved by several methods mentioned in Basic Algorithm Note.

Continue reading “算法设计与分析笔记0x05 —— 分治法(1)”

算法基础笔记0x05 —— 查找与选择

Search Algorithm

  • 给定一个排好序的数组,搜索输入x
  • Idea Maintain an interval between [l, r] where x may be. Shrink the interval as quickly as possible.
    • Initially the interval is all of A, i.e. l = 1, r = |A|.
  • Use a probe point m = (l + r) / 2.
    • If x < A[m], x can’t lie in [m, r], so keep searching in [l, m-1].
    • If x > A[m], keep searching in [m+1, r].
    • If l = r but x ≠ A[m], then x is not in A.

Continue reading “算法基础笔记0x05 —— 查找与选择”