8
\$\begingroup\$

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 
\$\endgroup\$
4
\$\begingroup\$

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

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!'
\$\endgroup\$
3
\$\begingroup\$

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)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.