1
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ This is not what binary search means. \$\endgroup\$ – kfx Mar 26 '17 at 16:05
  • \$\begingroup\$ As for your second question, see this: stackoverflow.com/questions/681649/… \$\endgroup\$ – kfx Mar 26 '17 at 16:06
  • \$\begingroup\$ @kfx Binary search is whether a digit is in an array. Why is this not a binary search example on a string? \$\endgroup\$ – Sam Hammamy Mar 26 '17 at 16:07
  • \$\begingroup\$ 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).) \$\endgroup\$ – kfx Mar 26 '17 at 16:11
  • \$\begingroup\$ @kfx so you have an example of a complete binary search that also implement the sort without using builtins? \$\endgroup\$ – Sam Hammamy Mar 26 '17 at 16:15
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Sam Hammamy Mar 26 '17 at 16:44
  • 1
    \$\begingroup\$ This is an alternative implementation, not a review. On Code Review, all answers should contain a review of the code provided by the author. \$\endgroup\$ – Mast Mar 26 '17 at 17:29
  • \$\begingroup\$ @Mast I copied some of my previous comments to the author to this answer and expanded it. \$\endgroup\$ – kfx Mar 26 '17 at 19:10
2
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – kfx Mar 26 '17 at 16:27
  • \$\begingroup\$ @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. \$\endgroup\$ – kraskevich Mar 26 '17 at 16:53

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.