Friedrich Ewald My Personal Website

Nearest binary search

To find the exact element or the next element that is greater than the target, use the following code. This algorithm returns an invalid index if the element that is searched for is greater than the greatest element in the array. This needs to be manually checked with s(items, target) == len(items). 

def s(items, target):
  l = 0
  r = len(items)
  m = (l + r) // 2

  while l < r:
    if items[m] == target:
      return m
    elif items[m] <= target:
      l = m + 1
    elif items[m] > target:
      r = m
    m = (l + r) // 2
  return m
    

l = [1,2,3,5,6,7,8,20,30,40,50]
targets = [0, 3, 4, 11, 12, 20, 30, 38]
for target in targets:
  idx = s(l, target)
  print(f"[{target:02}] Index: {idx} => {l[idx]}")
If you want to find the element which is exactly the element or less than the element, change the return value to return m - 1 instead. In the smallest case this will return -1 which means that the element searched for is smaller than the smallest on in the list. The resulting code looks like this: 
def s(items, target):
  l = 0
  r = len(items)
  m = (l+r) // 2

  while l < r:
    if items[m] == target:
      return m
    elif items[m] <= target:
      l = m + 1
    elif items[m] > target:
      r = m
    m = (l+r) // 2
  return m - 1

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts