Iterative binary search

Question

I have made a simple binary search algorithm with the assumptions that the input array is sorted and has only unique values.

def binary_search(input_array, value):
    """
    Iterative binary search in sorted array of unique int values.

    :param input_array: Sorted array of unique int values.
    :type input_array: list<int>
    :param value: The int value to search in input_array
    :type value: int
    :return: The index of value or -1 if it doesn't exist
    :rtype: int
    """
    result = -1
    previous_index_down = 0
    previous_index_up = len(input_array)
    current_index = int(math.floor(len(input_array[previous_index_down+1:previous_index_up]) / 2))
    while True:
        if input_array[current_index] == value:
            result = current_index
            break
        elif current_index == previous_index_down or current_index == previous_index_up:
            break
        elif input_array[current_index] > value:
            previous_index_up = current_index
            current_index = current_index - int(math.ceil(len(input_array[previous_index_down:previous_index_up+1]) / 2))
        elif input_array[current_index] < value:
            previous_index_down = current_index
            current_index = current_index + 1 + int(math.floor(len(input_array[previous_index_down+1:previous_index_up]) / 2))

        if previous_index_down == len(input_array) - 1:
            break
    return result

For test I used various inputs like the following:

test_list = [1,3,9,11,15,19,29]
test_val1 = 25
test_val2 = 15
test_val3 = 29
print binary_search(test_list, test_val1)
print binary_search(test_list, test_val2)
print binary_search(test_list, test_val3)

The results appear to be correct, but I am wondering if the implementation can be improved in terms of style and length. Also I don't know if there are inputs that may make it fail.

Answer 1

• Your lines are too long which makes things a little difficult to read. The next few points will help with that.
• In my opinion your variable names are too verbose. current_index could be replaced with i and most programmers will understand that as an indexing variable.
• When generating your current index, there is no reason to take the length of an array slice. The length of array[start:end] will generally be end - start. When that isn't true its because you are slicing outside of array bounds which probably means your search is over anyway. In any case, you don't really care about array length. You just want the mid point between the two indexes.
• there is no reason to pass the result of math.floor to int since both do essentially the same thing (int(2.6) gives 2). In fact, you can avoid both of these entirely by just using the integer division operator // (in python2 integer division is the default for 2 integers: 3/2==1
• while True is ok in some limited cases but I generally avoid it when I can because it can easily create infinite loops if you forget a break somewhere... and here you have a lot of breaks. Its not too hard to come up with a condition that will effectively bound your search, and reduce the number of conditions that you have to check for.

Following the above points gives much lighter looking code thats for the most part functionally the same:

def binary_search(input_array, value):
    result = -1
    # simplified variable names and index initializer
    down = 0
    up = len(input_array)
    i = (up - down+1) // 2
    while down < i < up:    # refactored out `while True`
        if input_array[i] == value:
            result = i
            break
        # remove `break` conditions now handled in `while`
        elif input_array[i] > value:
            up = i
            # remove unnecessary string slice, int cast, and math.floor calls
            i = i - (up+1 - down) // 2 # integer division
        elif input_array[i] < value:
            down = i
            i = i + 1 + len(input_array[down+1:up]) // 2 # integer division!

    return result