# Finding an element in a list

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


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

• For the curious, I can confirm that sorting and then using a binary search is not faster – wnnmaw Jan 16 '14 at 22:30
• 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. – Jaime Jan 16 '14 at 23:45

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!'


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.

continue