Searching a sorted list

This is like the bisect library module, but also returns whether or not the element is in the list, which saves having to do an extra comparison. Also, the function names make more sense.

sage.misc.search.search(v, x)[source]

Return (True,i) where i is such that v[i] == x if there is such an i, or (False,j) otherwise, where j is the position where x should be inserted so that v remains sorted.

INPUT:

  • v – list; which is assumed sorted

  • x – Python object

OUTPUT: boolean, integer

This is implemented using the built-in bisect module.

EXAMPLES:

sage: from sage.misc.search import search
sage: search([1,4,6,7,8], 6)
(True, 2)
sage: search([1,4,6,7,8], 5)
(False, 2)
sage: search(['a','c','d','h','z'], 'e')
(False, 3)

>>> from sage.all import *
>>> from sage.misc.search import search
>>> search([Integer(1),Integer(4),Integer(6),Integer(7),Integer(8)], Integer(6))
(True, 2)
>>> search([Integer(1),Integer(4),Integer(6),Integer(7),Integer(8)], Integer(5))
(False, 2)
>>> search(['a','c','d','h','z'], 'e')
(False, 3)