Skip to content

Implement binary search for searching in a set multi-indices

Damar Wicaksono requested to merge dev-121 into dev

Instead of a linear search, a binary search is now implemented as the algorithm for searching a multi-index entry in an array of lexicographically sorted multi-indices. The previous assumption is kept (now even more important), the array of multi-indices must be lexicographically sorted.

This commit should resolve Issue #121 (closed).

Several additional changes:

  • The utility function minterpy.jit_compiled_utils.get_match_idx() is renamed to minterpy.jit_compiled_utils.search_lex_sorted().
  • The utility function minterpy.jit_compiled_utils.index_is_contained() is renamed to minterpy.jit_compiled_utils.is_index_contained().
  • The test suite is extended to include a test for searching an element in a multi-index set; the test for index element containment is also simplified.
  • In-code documentation is updated for both utility functions.

Merge request reports

Loading