Find the right interval in a sorted arrary with duplicates given an input

Question

I'm struggling with an array problem which I am not quite sure how to solve with binary search properly.

Say x is a sorted array, with duplicated values. Given a x_input, find the index of the two adjacent element x_i, x_j in the sorted array such that x_i< x_input<=x_j. please note that, there are duplicates in the sorted array, so if there are duplicates on the right side of this interval, basically saying x_input<=x_j, we need to make sure j is the smallest index among all other elements with the same value. If there are duplicates on the left side, x_input > x_i, i has to be the largest index among all other elements with the same value. Then return [x_i, x_j].

a = [-2, -1, -1, -1, 2, 2, 5]

Some test cases are:

if x_input = -1.5, then return [0, 1]
if x_input = -1, then return [0, 1]
if x_input = 2, then return [3, 4]
if x_input = 2.1, then return [6, 7]

I'm new to algorithems and wondering if some one can shed some lights on how to solve this problem with binary search, or point me the leetcode question which I can refer to. Thank you.

Answer 1

Perform a binary search in the array for x_input without checking if x_input is found. At the end, high will be the left index of the interval (index of last element less than x_input) and low will be the right index (index of first element greater than or equal to x_input).

For example, in Python:

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