Skip to content
Advertisement

Pythonic Way to Get Unique Neighboring Integers in an Ordered List

Given an ordered integer list, return the largest integer less than N and smallest integer greater than N. If there is none for one, just print “X”.

Advertisement

Answer

As far as I know, this is the fastest solution possible.

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
    lm = -1
    while low <= high:
        lm = mid
        mid = (high + low) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
        if lm == mid:break
    return mid

def find_next_bigger(arr,n,i):
    while i < len(arr):
          if arr[i] > n:
              return arr[i]
          i += 1
    return arr[i] if i < len(arr) else "X"

def find_next_smaller(arr, n,i):
        while i >= 0:
            if arr[i] < n:
                return arr[i]
            i -= 1
        return arr[i] if i > 0 else "X"

def solution(arr, n):
    if n > arr[-1]:
        return arr[-1], "X"
    if arr[0] > n:
          return "X", arr[0]
    i = binary_search(arr, n)
    bigger = find_next_bigger(arr, n, i)
    smaller = find_next_smaller(arr,n,i)
    return smaller, bigger
User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement