# Extended Binary Search Function (python)

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


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].

• 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. – Tobi Alafin Jan 30 '19 at 0:54