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?

Jack Pierce-Brown
  • 1
  • 1
  • nice assignment, easy one thought.. – EsseTi Jul 10 '15 at 14:49
  • 2
    http://rosettacode.org/wiki/Binary_search#Python – Matt Jul 10 '15 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(). – smassey Jul 10 '15 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? – Jack Pierce-Brown Jul 10 '15 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. – smassey Jul 10 '15 at 15:40

0 Answers0