0

I have a list that I keep ordered with bisect with each insertion. When I insort with bisect

[1, 3, 5] # inserting 3

becomes

[1, 3, 3, 5]

But I want bisect to check if a number is found, if it exists don't duplicate it. Cancel the insertion. Is this thing achievable ? I checked the docs and google but the answer eluded me. Thanks in advance.

Note: I do not what to check the list before to see if the element is there, which would increase the complexity. I am trying to get this done without causing that.

Max Paython
  • 1,595
  • 2
  • 13
  • 25
  • Possible duplicate of [Is there a short contains function for lists in Python?](http://stackoverflow.com/questions/12934190/is-there-a-short-contains-function-for-lists-in-python) – DeepSpace Jul 17 '16 at 15:27
  • 1
    You might consider [`sortedcontainers.SortedSet`](http://stackoverflow.com/a/22567430) – GingerPlusPlus Jul 17 '16 at 15:30
  • Does that still use binary search to reduce insertion time ? – Max Paython Jul 17 '16 at 15:30
  • I don't know how it's implemented, but I'm almost sure it uses something with complexity `O(n) <= log2(n)` – GingerPlusPlus Jul 17 '16 at 15:33
  • So, you use binary search to find the place where to insert the number. Can't you modify that function so that it returns both the index and the element? Then just check if the element at that index already is the number you want to insert. – tobias_k Jul 17 '16 at 15:33
  • @tobias_k So if I can't override the bisect function that is handling this, I have to run the function two times to achieve what I want ? – Max Paython Jul 17 '16 at 15:36
  • I guess it is alright given that `log n` is such a low complexity. – Max Paython Jul 17 '16 at 15:39

0 Answers0