TestDrivenCode.comSignature
def find_interval(values: list[int], value: int) -> tuple[int, int]:
Test Code
import random
for length in range(100):
for _ in range(10):
values = [random.randrange(10) for _ in range(length)]
values.sort()
value = random.randrange(10)
start, end = find_interval(list(values), value)
for i in range(start, end):
assert values[i] == value
if start > 0:
assert values[start - 1] < value
if end < length:
assert values[end] > value
Description
Given a value, search the indices of the half-open range [start, end) that matches that value in a sorted array. For example, searching the value 1 in the sorted array [0, 1, 1, 1, 2, 3, 4] should result in the interval [1, 3).
Submit a Solution
Fastest Solutions
def find_interval(values: list[int], value: int) -> tuple[int, int]:
def find_left(lst, val):
lo, hi = 0, len(lst)
while lo < hi:
mi = (lo + hi) // 2
if lst[mi] < val:
lo = mi + 1
else:
hi = mi
return lo
def find_right(lst, val):
lo, hi = 0, len(lst)
while lo < hi:
mi = (lo + hi) // 2
if lst[mi] <= val:
lo = mi + 1
else:
hi = mi
return lo
start = find_left(values, value)
end = find_right(values, value)
return (start, end)
New Solutions
def find_interval(values: list[int], value: int) -> tuple[int, int]:
def find_left(lst, val):
lo, hi = 0, len(lst)
while lo < hi:
mi = (lo + hi) // 2
if lst[mi] < val:
lo = mi + 1
else:
hi = mi
return lo
def find_right(lst, val):
lo, hi = 0, len(lst)
while lo < hi:
mi = (lo + hi) // 2
if lst[mi] <= val:
lo = mi + 1
else:
hi = mi
return lo
start = find_left(values, value)
end = find_right(values, value)
return (start, end)