Asymptotic complexity of multiple binary search

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?

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

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:

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