Tuesday, October 19, 2010

Binary search

In cmpt454 quiz, a problem is related to binary search. But I though it is binary search tree. Now, I need clarify these two topics.

Binary search is an “algorithm” for search an item in a sorted array.
Binary search tree is a data structure, or called ordered search tree. It left subtree is smaller than the node, and right subtree is bigger than the node. When we traverse it in in-order, its elements are retrieved by order.

The similar point is that for search an item, both running time are in O(log(n)).

No comments:

Post a Comment