up vote 2 down vote favorite

Since binary search is \$O(log(n))\$. Consider this example where I am searching for the existence of e and l and f in the word.

Is this \$O(n log(n))\$ or \$O(3 log(n))\$ and thereby still \$O(log(n))\$?

def search(array, item):

    if not array:
        return False

    if len(array) == 1:
        return array[0] == item

    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]

    return search(left, item) or search(right, item)


def elfish(word, letters):
    """
    >>> elfish('', 'efl')
    False

    >>> elfish('whiteleaf', 'elf')
    True

    >>> elfish('whiteleaf', 'elf')
    True

    >>> elfish('unfriendly', 'elf')
    True

    >>> elfish('waffles', 'elf')
    True

    >>> elfish('waffles', 'elf')
    True

    >>> elfish('sameh', 'elf')
    False

    >>> elfish('wolf', 'elf')
    False

    """
    result = True
    for letter in letters:
        result = result and search(word, letter)
    return result


elfish('waffles', 'elf')

The pure Python way of doing this is:

if 'e' in word and 'l' in word and 'f' in word:
    return True

Is Python doing a binary search in the background?

share|improve this question
    
This is not what binary search means. – kfx 17 hours ago
    
As for your second question, see this: stackoverflow.com/questions/681649/… – kfx 17 hours ago
    
@kfx Binary search is whether a digit is in an array. Why is this not a binary search example on a string? – Sam Hammamy 17 hours ago
    
Binary search only works on sorted data. Here, the target string is not sorted. So you have to go through all of it to find the answer (which you actually do, so the runtime is O(n).) – kfx 17 hours ago
    
@kfxI see thanks for the clarification! – Sam Hammamy 17 hours ago
up vote 2 down vote accepted

There are multiple problems in your approach - but they are more at the conceptual level, not in the style of the code, which is just fine. The unit tests are also commendable. But:

  1. The algorithm you have coded is not the binary search algorithm.
  2. The code implements a recursive search algorithm in an unsorted array. It has \$O(n)\$ time complexity and \$O(log(n))\$ space complexity - a clearly suboptimal for this task. The space complexity comes from the recursive function calls and the fact that Python does not optimize tail recursion. While you do demonstrate that solving the problem with recursion is possible, it is not the best option in terms of efficiency.
  3. If you do implement binary search, sort the array first. To find the value I suggest using the functions from bisect module rather than reinventing the wheel, if this is a production code.
  4. The Python in operator does not use binary search, as it has to avoid sorting the string, so binary search would not work; however, it does use some advanced string search algorithms, so is better than a naive version.

In this loop:

    for letter in letters:
        result = result and search(word, letter)

it is clear that the answer will be False as soon as the first search() call fails. Therefore you can if not search(word, letter): return False for better efficiency, and don't need the result variable.

This is an alternative version that:

  1. Has \$O(max(||letters||, ||word||))\$ effective complexity (assuming \$O(1)\$ for set insertion and lookup) due to the use of counting sort.
  2. Increases the average efficiency by returning False immediately after the first missing character is encountered
def elfish(word, letters):
    present_characters = set()
    for c in word:
        present_characters.add(c)
    for letter in letters:
        if letter not in present_characters:
            return False
    return True
share|improve this answer
    
This is a great solution. But the whole point is to practice recursion. I didn't specify that. I will upvote the answer but if you can add an edit with recursion and a few notes I can accept it. – Sam Hammamy 16 hours ago
1  
This is an alternative implementation, not a review. On Code Review, all answers should contain a review of the code provided by the author. – Mast 16 hours ago
    
@Mast I copied some of my previous comments to the author to this answer and expanded it. – kfx 14 hours ago
up vote 2 down vote

You can't use binary search on an unsorted string (it can return an incorrect result). If you decide to sort the string, the complexity would be O(n log n), which is worse than a linear search. So I'd recommend to stick to a standard "pythonic" way to do it (using the in operator).

share|improve this answer
    
For searching 3 characters "in" would be faster, but it would not scale - say what if he needs to search 10 characters? Counting sort would be the fastest way here, if performance is the main issue. – kfx 17 hours ago
    
@kfx It really depends on the usage patterns. If the code handles a lot of different strings but the number of queries for each individual string is very low, a simple linear search can the fastest solution. If the number of queries per string is much higher, the situation is different, sure. – kraskevich 16 hours ago

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.