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

• greybeard: (Welcome to CR.SE!) next few points will help with [improving code readability with shorter lines] You can have nested lists: just "indent" the items to be nested some (one blank seems to suffice). (Then again, I see only one point related to line length.) Good job in adding in-line comments. Personally, I would have preferred to see the doc string reproduced.
• David Foerster: int() only does the same as math.floor() for non-negative numbers (which is all we care for here). For negative numbers int() behaves like math.ceil().
• Vasilis: Thanks for the reply, great points! I guess without having to call len() and floor() in every iteration your code is also faster, not just cleaner.