In python, while implementing the binary search algorithm, which math function is optimal to be used to find out the mid value - floor or ceil ?
3 Answers
You don't need to use either ceil or floor function for implementing binary search in python. Depending on the problem, you have to round the mid value up or down.
mid = low + (high-low)/2 #rounds down the mid value
mid = low + (high-low+1)/2 #rounds up the mid value
Try to solve these two problems, you will get an idea how this works.
- Given an array A and a target value, return the index of the first element in A equal to or greater than the target value
- Given an array A and a target value, return the index of last element which is smaller than target value.
First try these problems on your own and if you get stuck, refer to the this.
1 Comment
Mark Dickinson
Your use of
// for comments is a bit confusing here. I suggest using // for the division and # for comments.From what I understand about floor and ceil, there does not appear to be a more optimal option. You may want to find out more in this site.
1 Comment
txsaw1
I think your question needs to be a bit more concise in terms of what you are doing with the alogorithm, do you have any script of your work?
You actually do not need to use ceil or floor @shivam_mitra mentioned. Here is a binary search algorithm if need it.
def bSearch(L, e, low, high):
"""
L: is a sorted list
e: is the targeted number
low: is the lowest value of the list
hight: is the highest value of list
"""
if len(L) == 0: # empty list
return False
if high == low: # if the list is one element
return L[low] == e
mid = low + int((high - low)/2)
if L[mid] == e: # If the midpoint is the targeted number
return True
if L[mid] > e: # check if the number is in the lower half of the list
return bSearch(L, e, low, mid - 1)
else: # otherwire it is in the higher of the list
return bSearch(L, e, mid + 1, high)
bisectwhich has examples of searching a sorted list.