How to find the highest number less than target value in a list?

Question

I am trying to write a binary search that takes a sorted list and finds the largest number less than a target value:

def binary_max(list, target)
    hi=len(list)-1
    lo=0
    while lo<=hi:
        mid=(hi+lo)//2
        midval=list[mid]
        if midval > target:
            hi=mid-1
        elif midval <= target:
            lo=mid
        if hi==lo:
            break
    return(list[mid])
pass

However, when for example there is a list with length 2, hi=1 and the mid value will always be stuck on lo.

Is there anyway to avoid this problem?

Repp

It might sound silly but: Can you update your question to include the full function and the code to call it? – Overskirt

seldon the while loop is idiomatic in Python unless it is an infinite loop (while True) – Lanthanum

@PauloScardine, Yet if you look in bisect.py... – Seeing

@gnibbler: this module looks like C translated to Python, but I can't think of a better algorithm. :-) – Lanthanum

Answer 1

The bisect module provides functions to do exactly that. Use bisect.bisect.

Hypotension

can you show how bisect would work when target is not in list? – Alfredoalfresco

@Alfredoalfresco docs are pretty clear on that. The returned insertion point i partitions the array a into two halves so that all(val <= x for val in a[lo : i]) for the left side and all(val > x for val in a[i : hi]) for the right side – Hypotension

Answer 2

When you break out of the loop, mid still contains the value from the previous iteration.

Bridgeboard

Answer 3

You can find the highest number less than the target value as follows:

n = int(input())
arr = map(int, input().split())
arr = list(arr)
indices = [v for i,v in enumerate(arr) if v != max(arr)]
print(max(indices))
    

Here I'm demonstrating it for target value = max value in the list. You can change max value to any target value you want.

Hussite

Answer 4

Here is a simple function to do that. Hope it works:

def bin_search(list, target):
    if target not in list:
        return None
    list.sort()
    return list[list.index(target)-1]

Saiga

you could simplify it like this list[list.index(target)-1] – Halves

He does, I was just saying how you could simplify the last two lines of your answer. – Halves

Doesn't work if target value is not in list - there's no assumption of that by OP. – Alfredoalfresco