Binary search misfunctioning

[group256]

Dear experts in Python,

I have written a binary search method that receives a list of float and one new float item. It needs to look for the proper index for that item to be placed and return that index. To make it simple, I give an example:

imagine a list that is empty at first ([]) is given to this binary search as well as a new value, say 110.2

Now the function should return 0. Cause there is no item there. so my list now is [110.2].

Now if the method is called and the list is passed to it with new value of 112.3, it should return me index of 1 ---> so list is : [110.2, 112.3].

My method works fine with it, but when I finish inserting, last value in the list is always out of sort, like [110.2, 112.3, 121.4, 154.7, 113.6]

Here is the code:

def _Binary_Search_Get_Index (list, newValue):
    ''' Uses binary search to get the proper index to place item
    Returns index, if not found, returns -1'''
    min = 0; max = len(list) - 1
    while 1:
        if max < min:
            return m 
        m = (min + max) / 2
        if list[m] < newValue:
            min = m + 1
        elif list[m] > newValue:
            max = m - 1
        else:
            return m

Thank you.

[nezachem]

What is m at line 7?

[group256]

m is the result.

[TrustyTony]

You have bad variable names, all min, max and list are used in Python and unavailable for you when they are shadowed. Minimum you should do is to add _ in end of variable best is to use more specific free names.

What is value of m when parameter list == []? Did you test the test cases you gave in your post?

[vegaseat]

Binary search also needs a sorted list.

[lrh9]

Isn't this what the bisect module is for?

[TrustyTony]

If you use binary search correctly, you can insert things in correct order so binary search continues to work. You should test all your test cases and add printing of all results from this function and list before and after insert to given position.

And yes, it is easy to do same thing with standard library bisect.bisect, I was assuming that this was exercise, but if you can choose, better to use surely tested standard routine.

[lrh9]

I can't tell if this is an exercise.

Even if it is, the bisect source can still serve as an inspiration and guideline.

It's strange how people don't realize that a lot of things are in the standard module library and the source is available for most of it.

[group256]

Thank you very much everyone.

This is actually not an exercise, this is for work.

Secondly, Irh9 I do know about the name of bisect, but I didn't use it for 2 reasons:

1- I am modifying someone else's code who is a pro and I trust the code. But the code originally is a binary search which returns the value if found, not the index. Once I modified it, it had this bug.

2- I knew about bisect but I didn't know about its performance as it's really crucial in my current work that the code should have good performance as well as robustness.

But somehow, if you guys think that bisect is a fully trustable module, I would move the code to it.

Many many thanks.

[lrh9]

I do think you should use bisect.

It works.

If you can be sure that your value will fall between two indices, you can specify a lower bound and an upper bound to restrict the search. (Thus reducing search times.)

The implementation isn't much different from your own.

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

[group256]

So OK, I tried bisect, it works although it seems it has limitations too.

Correct me if I'm wrong but it seems that if the list is not ascending, it always returns the most right index.

[lrh9]

Hm. It seems like bisect assumes ascending order. I hadn't thought of descending order.

You can either write your own function or you can keep your data in ascending order until you need descending order.

It's possible to get a reverse iterator over a sequence using the function reversed.
A slice with a negative step will have reversed elements. Example: L[::-1]

[TrustyTony]

Check out this StackOverFlow code:

I include answer, which is modification of library routine already posted, here also for convenience:

def reverse_insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

[group256]

Thanks a lot tonyjv,

I will take a look at it and will let you know if I manged to get it to work.

Many thanks for your help.

[group256]

So,

OK, this doesn't solve anything. If I was to write code for it, I would use my own code. Somehow it turned out that I didn't need to use descending and I was lucky in that case.

So I sign this thread as solved and thanks to all people helping out here.