[Algorithms] 2 - Review(2)

4. Binary Search

Definitions

• It is designed to enhance the linear search

• Finds the median value, and compare with the target value and throw away half of the array including the median value if the median value does not match with the target value.

Things to keep in mind

• Time complexity: O(logn)

• The array needs to be sorted.

5. Heaps

Definitions

• Basically an array, but structured to function as heap.

• Min heap: The smallest value is the root

• Max heap: The greatest value is the root

Things to keep in mind

• Parent: floor(index-1/2)

• Left: index*2 + 1

• Right: index*2 + 2

• Insertion takes O(logn) (Keep swapping values)

6. Binary Tree

Defintions

• Full Tree: Every node can have either zero or two children.

• Complete Tree: Every level has to be full except the last level + the last level nodes need to be pushed to left as much as possible.