Binary search Algorithm - Python

Question

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 ?

Are these numerical values being searched? Or is it a general binary search? — Peter Wood, Sep 03 '15 at 06:02
Python has a builtin module [**`bisect`**](https://docs.python.org/2/library/bisect.html) which has [examples of searching a sorted list](https://docs.python.org/2/library/bisect.html#searching-sorted-lists). — Peter Wood, Sep 03 '15 at 06:05

shivam mitra · Accepted Answer · 2015-09-03T07:15:31.363

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.

Your use of `//` for comments is a bit confusing here. I suggest using `//` for the division and `#` for comments. — Mark Dickinson, Sep 03 '15 at 06:56

score 0 · Answer 2 · edited May 23 '17 at 12:09

0

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.

edited May 23 '17 at 12:09

Community

1
1

answered Sep 03 '15 at 06:07

txsaw1

121
13

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? – txsaw1 Sep 04 '15 at 07:08

score 0 · Answer 3 · answered Dec 25 '16 at 21:15

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)

Binary search Algorithm - Python

3 Answers3