0

I know one way to determine if an object is in an array:

if object in array:
    print "object is in array"

However this can be slow if the array is large. I assume the algorithm works by looking at every object in the array and compares it to the object being searched for. If know the array is sorted (low to high) the algorithm can stop looking once an object in the array is larger than the object being searched for (and conclude the object is not in the array). How would this be efficiently implemented in Python?

Improve this question
5
  • nice assignment, easy one thought.. Commented Jul 10, 2015 at 14:49
  • 2
    rosettacode.org/wiki/Binary_search#Python Commented Jul 10, 2015 at 14:49
  • The real problem is that the elements probably shouldn't be in an array if the main operation is search. That's where hashes shine: either keys of a dict or simply using a set(). Commented Jul 10, 2015 at 14:58
  • @smassey I have a function that generates primes up to a inputted value. I'm storing those values in an array currently (the primes are in order). Then if I want to check if a number is prime I search through the array of primes to see if the number is there. Should I not be using an array? Commented Jul 10, 2015 at 15:12
  • Certainly so, you are correct to keep them in an array (they're sorted by default, i thought this was an intermediate step in your case). In that case I'll change my view: a binary search of the list will probably be the most efficient. Commented Jul 10, 2015 at 15:40
Related questions
12224
How can I remove a specific item from an array in JavaScript?
13112
What does the "yield" keyword do in Python?
8107
Does Python have a ternary conditional operator?
Load 7 more related questions Show fewer related questions

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.