Lecture overview -- Keyboard shortcut: 'u'  Previous page: Sample use of Sort in <b><kbd>List<T></kbd></b> -- Keyboard shortcut: 'p'  Next page: Overview of the class <b><kbd>LinkedList<T></kbd></b> -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Textbook -- Keyboard shortcut: 'v'  Help page about these notes  Alphabetic index  Course home  Page 16 : 36
Object-oriented Programming in C#
Collection Classes
Sample use of BinarySearch in List<T>

An illustration of two overloads of BinarySearch

/user/normark/oop-csharp-1/sources/c-sharp/collections/list/3/prog.csSample uses of List.BinarySearch.


/user/normark/oop-csharp-1/sources/c-sharp/collections/list/3/outputOutput from the BinarySearch program.


/user/normark/oop-csharp-1/sources/c-sharp/collections/list/3/prog-not-found.csSearching for a non-existing Point.


/user/normark/oop-csharp-1/sources/c-sharp/collections/list/3/output-not-foundOutput from the BinarySearch program - non-existing Point.


  • Lessons learned

    • Binary search can only be done on sorted lists

    • In order to use binary search, we need - in general - to provide an explicit Comparer object

    • Binary search returns a (non-negative) integer if the element is found

      • The index of the located element

    • Binary search returns a negative integer if the element is not found

      • The complement of this number is a ghost index

      • The index of the element if it had been in the list