3
\$\begingroup\$

I wrote a function to find the closest value in a list to a given search value. What prompted me to write it was as boilerplate for a prime number problem so I could find the closest prime to a given number.

My Code

'''
*   This function finds the closest value in a sorted list to a given search value.
*   Parameters:
        *   `lst` is the list to be searched.
        *   `item` is the value to be searched for.
        *   `current` stores the current best match.
        *   `control` controls the search behaviour of the function.
            *   `up` means find the closest value >= to `item`.
            *   `down` means find the closest value <= to `item`.
            *   `up(strict)` means find the closest value > to `item`.
            *   `down(strict)` means find the closest value < to "`tem`.
            *   `neutral` means find the closest value to `item`.
*   Return:
        *   Returns the closest match in `lst`.
        *   None is returned if no value in the list satisfies the condition (e.g an empty list).
'''

def mins(lst, f = None):
    mn = min(lst) if f is None else min(lst, key = f)
    return (i for i in lst if i == mn)

def maxes(lst, f = None):
    mx = max(lst) if key is None else max(lst, key = f)
    return (i for i in lst if i == mx)

def xBinSearch(lst, item, control="neutral", current=None):
    n = len(lst)
    var = round(n/2)
    if n > 1:
        if control == "up":
            if lst[var] == item:
                return lst[var]
            elif lst[var] > item:   #The solution is in `lst[:var+1]`.
                current = lst[var] if current == None or abs(current - item) > abs(lst[var] - item) else current    #Update "current" to contain the current closest match.
                return xBinSearch(lst[:var], item, control, current)    
                #Search the eligible space. If the solution is `lst[var]`, it is already stored in `current`.
            else:   #The solution is not in `lst[:var+1]`
                return xBinSearch(lst[var+1:], item, control, current) if var + 1 < n else current  
                #Search the eligible space if it exists, else (if there is no where left to search), return the current best match.

        elif control == "down":
            if lst[var] == item:
                return lst[var]
            elif lst[var] < item:   #The solution is not in `lst[:var]`.
                current = lst[var] if current == None or abs(current - item) > abs(lst[var] - item) else current    #Update "current" to contain the current closest match.
                return xBinSearch(lst[var:], item, control, current)    #Search the eligible space.
            else:   #The solution is not in lst[var:]
                return xBinSearch(lst[:var], item, control, current) if var + 1 < n else current    
                #Search the eligible space if it exists, else (if there is no where left to search), return the current best match.

        elif control == "up(strict)":
            if lst[var] > item: #The solution is in `lst[:var+1]`.
                current = lst[var] if current == None or abs(current - item) > abs(lst[var] - item) else current    #Update "current" to contain the current closest match.
                return xBinSearch(lst[:var], item, control, current)    
                #Search the eligible space. If the solution is `lst[var]`, it is already stored in `current`.
            else:   #The solution is not in `lst[:var+1]`
                return xBinSearch(lst[var+1:], item, control, current) if var + 1 < n else current  
                #Search the eligible space if it exists, else (if there is no where left to search), return the current best match.

        elif control == "down(strict)":
            if lst[var] < item: #The solution is not in `lst[:var]`.
                current = lst[var] if current == None or abs(current - item) > abs(lst[var] - item) else current    #Update "current" to contain the current closest match.
                return xBinSearch(lst[var:], item, control, current)    #Search the eligible space.
            else:   #The solution is not in lst[var:]
                return xBinSearch(lst[:var], item, control, current) if var + 1 < n else current    #Search the eligible space if it exists, else (if there is no where left to search), return the current best match.

        else:
            check = [("b", lst[var], abs(lst[var]-item))]   #`check[0]` => `var`.
            if var-1 >= 0:
                check.append(("a", lst[var-1], abs(lst[var-1]-item)))       #`check[1]` => `var-1`.
            if var+1 < n:
                check.append(("c", lst[var+1], abs(lst[var+1]-item)))       #`check[2]` => `var+1`.
            mn = [x for x in mins(check, f = lambda x: x[2])]   #The closest values to `item` from among the slice.

            if "a" in mn and "c" not in mn:     #The solution is not in `lst[var+1:]`
                current = check[1][1] if current == None or abs(current - item) > check[1][2] else current
                return xBinSearch(lst[:var+1], item, control, current)
            elif "b" in mn and ("a" not in mn and "c" not in mn):   
                #The solution is neither in `lst[:var]` nor in `lst[:var+1]` so is therefore `lst[var]`.
                return lst[var]
            elif "c" in mn and "a" not in mn:       #The solution is not in `lst[:var]`
                current = check[2][1] if current == None or abs(current - item) > check[2][2] else current
                return xBinSearch(lst[var+1:], item, control, current)
            else:   #The solution is in either lst[:var] or lst[var+1:]
                current = check[0][1] if current == None or abs(current - item) > check[0][2] else current
                return min([xBinSearch(lst[:var], item, control, current), xBinSearch(lst[var+1:], item, control, current)], key = lambda x: abs(x - item))

    else:
        if n == 1:
            if control == "up":
                if lst[0] >= item:  #If it is an eligible solution.
                    current = lst[0] if current == None or abs(current - item) > abs(lst[0] - item) else current
                    #Modify `current` accordingly.
            elif control == "down":
                if lst[0] <= item:  #If it is an eligible solution.
                    current = lst[0] if current == None or abs(current - item) > abs(lst[0] - item) else current
                    #Modify `current` accordingly.
            if control == "up(strict)":
                if lst[0] > item:   #If it is an eligible solution.
                    current = lst[0] if current == None or abs(current - item) > abs(lst[0] - item) else current
                    #Modify `current` accordingly.
            elif control == "down(strict)":
                if lst[0] < item:   #If it is an eligible solution.
                    current = lst[0] if current == None or abs(current - item) > abs(lst[0] - item) else current
                    #Modify `current` accordingly.
            else:
                current = lst[0] if current == None or abs(current - item) > abs(lst[0] - item) else current
                #Modify `current` accordingly.
        return current
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

Your xBinSearch is too large, and too recursive.

Most binary searches are over quickly, because log2(n) is small. So you certainly can use a recursive approach. But, especially in an interpreted language like Python, setting up and tearing down function calls is a lot more expensive than iterating in a while loop. So if you have any urge to improve performance, switch from recursion to iteration.

That said, you have made your code much too fluffy. "Up", "down", "up(strict)", what is all this?

Step back and think about the problem.

You want to find the closest value to a given query. There are two possibilities:

  1. The value is in the list. Return it.
  2. The value is not in the list. Return the closest value.

Only case two is interesting from a binary-search perspective. You might not find the value, but you should be able to find the greatest-value-less-than your query, unless all values in the list are greater.

If you find some GVLT value, then compare that value and the next value in the list: one of them is "closest". return a if (abs(q-a) < abs(q-b)) else b.

If you find no GVLT value, all values are greater. Just return the_list[0].

\$\endgroup\$
1
  • \$\begingroup\$ For the use case that inspired the function, I actually need the smallest value in the list >= the provided search value ("up" in my terminology). I'll look at implementing it with iteration, when next I try to refactor. \$\endgroup\$ Jan 30, 2019 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.