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
