2
\$\begingroup\$

I have written this function to perform a binary search on an array, given begin/end indices and a value to look for in the supplied array:

def binarySearch(array, beginIndex, endIndex, value):
    while (beginIndex < endIndex):
        mid = (beginIndex + endIndex) / 2
        if array[mid] < value:
            beginIndex = mid + 1
        elif array[mid] > value:
            endIndex = mid - 1
        else: #equal
            return mid

    if array[beginIndex] == value:
        return beginIndex
    else:
        return -1

Test cases / output:

print binarySearch([2,3], 0, 1, 2)
 0
print binarySearch([2,3], 0, 1, 3)
 1
print binarySearch([2,3], 0, 1, -1)
-1
print binarySearch([2,3,3,3,4,5], 0, 5, 3)
 2

So it works as intended. I'm interested in feedback mostly from a functional perspective, but I'm open to anything else that might catch your eye.

\$\endgroup\$
  • 1
    \$\begingroup\$ Is this Python 2 or 3? Because the behaviour of the / operator is different. \$\endgroup\$ – Greg Hewgill Sep 30 '15 at 2:33
  • \$\begingroup\$ @GregHewgill, good question. I am using Python 2.7.8, your advice is appreciated. Find any issues? Thanks. \$\endgroup\$ – Lin Ma Sep 30 '15 at 3:08
  • 1
    \$\begingroup\$ You could return ~beginIndex instead of -1, so when not found, you return the ones complement of the insertion position (negative). That is what java does. \$\endgroup\$ – Joop Eggen Sep 30 '15 at 14:54
  • \$\begingroup\$ Thanks @JoopEggen, always nice to learn from you and I corrected indent issue and // issue you pointed out. Besides style/return method issues, do you see any functional issues in my code from a binary search tree perspective? :) \$\endgroup\$ – Lin Ma Oct 1 '15 at 22:29
3
\$\begingroup\$
  1. Your function doesn't have docstrings. Docstrings are good because they give you an opportunity to tell users of your code how to use it. I had to read the whole code to determine that the binary search you were referring to was for element extraction on a (presumably sorted) list.

  2. You don't check for (or even document) that your function only works on sorted lists. For example binarySearch('acb', 0, 2, 'b') gives -1 which might not be what users expect. You could add an assert array == sorted(array) statement to guard against unsorted arrays being passed in, or at the very least mention the requirement for sortedness in the docstring.

  3. You could easily supply default arguments for beginIndex and endIndex in the common use case that the search should start on the whole array. The case of endIndex is a bit tricky since the default value depends on the length of the whole array. But you could so something like:


def binarySearch(array, value, beginIndex=0, endIndex=None):
    """Docstring you need to add"""
    if endIndex is None:
        endIndex = len(array) - 1
    # rest of code

That way, users would not always have to supply arguments for beginIndex and endIndex if they didn't feel like it. Notice how I had to re-order the parameter to achieve this effect, because arguments with default values must all be listed after arguments with no default (and you won't likely ever want a default value for value).

  1. You could make the code forward-compatible with Python 3 by adding a from __future__ import division at the top and using // instead of /.

  2. For consistency with most other regular Python functions, you might want to raise ValueError or something similar instead of return -1 when the search does not succeed. I'm only slightly joking when I say that Pythonic users might interpret a -1 as meaning that the desired value was found at the end of the array!

  3. You don't use PEP8 style recommendations. binary_search() and begin_index would be preferred names relative to binarySearch() and beginIndex.

\$\endgroup\$
  • \$\begingroup\$ F, thanks for all the comments. From functionality perspective, if I assume sorted list, any bugs? Thanks. \$\endgroup\$ – Lin Ma Sep 30 '15 at 6:07
  • 2
    \$\begingroup\$ // is available even without the future import (from Python 2.2). \$\endgroup\$ – Janne Karila Sep 30 '15 at 13:09
  • \$\begingroup\$ @JanneKarila, what is the benefit of using //? Maybe I see too many old-style code and rare see // used. Please feel free to correct me if I am wrong. \$\endgroup\$ – Lin Ma Sep 30 '15 at 22:40
  • \$\begingroup\$ @LinMa It behaves the same on both Python 2.x and 3.x \$\endgroup\$ – Janne Karila Oct 1 '15 at 5:05
  • \$\begingroup\$ @holroy, thanks and always nice to learn from you and I corrected indent issue and // issue you pointed out. Besides style/return method issues, do you see any functional issues in my code from a binary search tree perspective? :) \$\endgroup\$ – Lin Ma Oct 1 '15 at 22:30

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.