Finding an element in a list

Question

I'm kind of new to Python. So, I wonder which method is better to use in a function to find an element in a list.

First:

def search_binary(xs,target):
 count = 0
 for i in xs:
 if i == target:
 return count
 count = count +1
 else:
 count = count +1
 continue
 return -1

Second:

def search_binary(xs, target):
 lb = 0
 ub = len(xs)
 while True:
 if lb == ub: 
 return -1
 mid_index = (lb + ub) // 2
 item_at_mid = xs[mid_index]
 if item_at_mid == target:
 return mid_index 
 if item_at_mid < target:
 lb = mid_index + 1 
 else:
 ub = mid_index 

Answer 1

If your list is sorted you can use binary search (your second code), and it will be faster for large lists, but if it's unsorted you'll have to keep to linear search. The Python library provides fast implementation of both methods, so you really don't need to roll your own:

>>> a = range(10)
>>> a.index(4) # linear search
4
>>> import bisect
>>> idx = bisect.bisect(a, 4) # binary search
>>> if a[idx-1] == 4:
... print idx - 1
... else:
... raise ValueError('item not in list')
... 
4

• wnnmaw: For the curious, I can confirm that sorting and then using a binary search is not faster
• Jaime: That depends on how much searching you have to do... Sorting a list of n items takes O(n log n) time, but then you can do a search in O(log n) time. So if you have to search for m items, sorting then searching will take time O((m+n) log n), while the linear search takes time O(mn). If you have to search for a single item then it doesn't pay off to first sort, if you have a million, then it may.

Answer 2

Bisect is the 'right' answer for serious applications where speed matters. It sounded to me like you're asking a style question. On that assumption:

def search_binary(xs,target): # enumerate generates the indices for you
 for count, val in enumerate(xs):
 if val == target: 
 return count # no need to explicitly continue either
 return -1

Is the simplest loop style version. You could write nearly the same thing as:

def search_binary_with_comprehension (xs, target):
 return [ count for count, val in enumerate(xs) if val == target]
 # list comprehensions ftw!

which would return a list of all the indices in the list with the target val, and an empty list if the target was not found

For the simplest case - just finding an object in a list, the real python way to do it is:

found_index = xs.index(target) # assuming xs is a list or tuple

which will return the index if it can, and raise a ValueError if the target is not present, or

target in xs

which will be true if target is anywhere in xs and false if not:

if not target in xs:
 print 'target is not in list!'

Answer 3

In your first piece of code...

count = count + 1

can be rewritten as:

count += 1

Secondly, putting

count = count + 1

under a return statement is silly. The return statements boots you out of the function meaning that code will never be run.

Finally, adding

continue

at the end of a loop is also a bit silly. Your loop is going to reiterate regardless of whether you force it along with a continue or not.

To answer your question, the first piece of code is more pythonic in nature. (Readability)

• Shift 'n Tab: I'm sorry but count += 1 doesn't work in python :)