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 – a list, which is assumed sorted
x – Python object
OUTPUT:
bool, int
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)