current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 7 down vote favorite

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
share|improve this question

3 Answers 3

up vote 4 down vote

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
share|improve this answer
    
For the curious, I can confirm that sorting and then using a binary search is not faster –  wnnmaw Jan 16 '14 at 22:30
1  
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
up vote 3 down vote

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!'
share|improve this answer
up vote 3 down vote

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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