Finding Items in a Sorted List

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Finding Items in a Sorted List

Program defines the two methods used to locate items in a sorted list. Both of these methods make use of the FindOffset method described above.

program10157
Program: SortedListAsArray class Find and FindPosition methods.

The Find method takes a given object and finds the object contained in the sorted list which matches (i.e., compares equal to) the given one. It calls FindOffset to determine by doing a binary search the array index at which the matching object is found. Find returns a reference to the matching object, if one is found; otherwise, it returns null. The total running time of Find is dominated by FindOffset. Therefore, the running time is .

The FindPosition method also takes an object, but it returns a Cursor instead. FindPosition determines the position in the array of an object which matches its second argument.

The implementation of FindPosition is trivial: It calls FindOffset to determine the position at which the matching object is found and returns an instance of the private class MyCursor. (The MyCursor class is derived from the class of the same name shown in Program ). The MyCursor overrides the inherited InsertAfter and InsertBefore methods with methods that throw an InvalidOperationException. These insert operations are not provided for sorted lists because they allow arbitrary insertion, but arbitrary insertions do not necessarily result in sorted lists.

The total running time of the FindPosition method is dominated by FindOffset. Therefore like Find, the running time of FindPosition is .