CODEWITHSUNDEEP
pythonbinary-search
user2906979
user2906979

Reputation: 315

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

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?

Upvotes: 13

Views: 20620

Answers (4)

shx2
shx2

Reputation: 64288

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

Upvotes: 5

Nischay Namdev
Nischay Namdev

Reputation: 593

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.

Upvotes: 0

JadedTuna
JadedTuna

Reputation: 1823

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]

Upvotes: -1

NPE
NPE

Reputation: 500227

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

Upvotes: 0

Related Questions