0

Whenever I needed to check whether an item belongs to a given group I used to store the elements in a list and use in to make the check:

def is_in_list(element, l):
    if element in l:
        print('yes')
    else:
        print('no')

is_in_list(2, [1,2,3])

This solution does not require for the elements to be sorted, or for the list to even be made exclusively of numbers. I guess that in the specific case I already know that the elements are all integer numbers and that they are sorted there must be a more efficient way to do this.

What is the best way to organize my data so that it will be quick to verify whether a given number belongs to a list?

(Ps. I call it "list", but it is not important for it to be a list specifically, and if it is recommended, I can very well use arrays or dictionaries instead).

3sm1r
  • 520
  • 4
  • 19
  • [binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm) – Mauxricio Jan 20 '23 at 10:20
  • 1
    If your list doesn't contain repeated elements use a set. If you have repeated elements you can use a dictionary where the key is the element and the value how many times this element appears. In both cases, checking if an element exists can be done in constant time, which is better than a sorted list and much better than an unsorted list – Sembei Norimaki Jan 20 '23 at 10:20
  • 1
    Python has binary search built in in the `bisect` module, as seen in the duplicate, which will work on your sorted list as-is. For an O(n) up-front cost, you can also use a `set`, which is faster. – Ry- Jan 20 '23 at 10:25

0 Answers0