COMPSCI 61B Lecture Notes - Lecture 26: Total Order, Binary Search Algorithm, Big O Notation
Document Summary
This is a useful task in its own right. Equivalent items are adjacent, allowing rapid duplicate finding. Items are in increasing order, allowing binary search. Can be converted into various balanced data structures. Also provide interesting case studies for how to approach basic computational problems. Some of the solutions will involve using data structures we"ve studied. An ordering relation < for keys a, b, and c has the following properties. Exactly one of a < b, a = b, b < a is true. An ordering relation with the porperties above is also known as total order . A sort is a permutation (re-arrangement of a sequence of elements that puts the keys into non-decreasing order relative to a given ordering relation. Ordering relations are typically given in the form of compareto or compare methods. Not that with respect to the order defined, the = get if just checking for lengeth.
