Binary search function

Question

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.

Answer 1

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

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

5. 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!

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