Searching a sorted list?

Question

What is a Pythonic way to search or manipulate sorted sequence?

I believe the question is trying to be "canonical" or "generic" and so the meaning of "sequence" may be using the [Python documentation definition of a `sequence` (i.e. python 2.x "There are seven sequence types: strings, Unicode strings, lists, tuples, bytearrays, buffers, and xrange objects.")](https://docs.python.org/2/library/stdtypes.html#sequence-types-str-unicode-list-tuple-bytearray-buffer-xrange) — Trevor Boyd Smith, Oct 25 '17 at 12:42
Duplicate: [Binary search (bisection) in Python](https://stackoverflow.com/questions/212358) — Karl Knechtel, Mar 06 '23 at 07:26

score 32 · Answer 1 · edited Aug 05 '15 at 09:00

32

bisect is part of the standard library - is that the sort of thing you're looking for?

edited Aug 05 '15 at 09:00

Raghav RV

3,938
2
22
27

answered Jul 07 '10 at 16:07

Daniel Roseman

588,541
66
880
895

21

that doesn't explain how to search for the value in the list. – Jean-François Fabre Feb 05 '18 at 16:27
From the link you provided: "The bisect() functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks." – MrMartin Dec 12 '18 at 06:27
@MrMartin what's the difference between finding an insertion point in a sorted list, and performing a "common search task" on a sorted list? – theonlygusti Mar 13 '21 at 12:59
@theonlygusti I believe the point is that helper functions may be needed, and that search typically requires finding all matches, rather than only the first – MrMartin Mar 15 '21 at 11:18
Solution in [this](https://stackoverflow.com/a/49281681) answer. – Basj Feb 22 '22 at 11:47

score 26 · Answer 2 · answered Apr 17 '14 at 19:22

It's worth noting that there are a couple high-quality Python libraries for maintaining a sorted list which also implement fast searching: sortedcontainers and blist. Using these depends of course on how often you're inserting/removing elements from the list and needing to search. Each of those modules provide a SortedList class which efficiently maintains the items in sort order.

From the documentation for SortedList:

L.bisect_left(value)
    Similar to the bisect module in the standard library, this returns
    an appropriate index to insert value in L. If value is already present
    in L, the insertion point will be before (to the left of) any existing
    entries.

L.bisect(value)
    Same as bisect_left.

L.bisect_right(value)
    Same as bisect_left, but if value is already present in L, the
    insertion point will be after (to the right of) any existing entries.

Both implementations use binary search to find the correct index of the given value. There's a performance comparison page for choosing between the two modules.

Disclaimer: I am the author of the sortedcontainers module.

score 19 · Accepted Answer · edited Feb 22 '22 at 11:46

Python:

import bisect

def find_in_sorted_list(elem, sorted_list):
    # https://docs.python.org/3/library/bisect.html
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(sorted_list, elem)
    if i != len(sorted_list) and sorted_list[i] == elem:
        return i
    return -1

def in_sorted_list(elem, sorted_list):
    i = bisect.bisect_left(sorted_list, elem)
    return i != len(sorted_list) and sorted_list[i] == elem

L = ["aaa", "bcd", "hello", "world", "zzz"]
print(find_in_sorted_list("hello", L))  # 2
print(find_in_sorted_list("hellu", L))  # -1
print(in_sorted_list("hellu", L))       # False

@Basilevs this should be the accepted answer :) – Basj Feb 22 '22 at 11:47 — Basj, Feb 22 '22 at 11:47

Searching a sorted list?

3 Answers3

Linked

Related