A video player keeps the timestamps of its decoded frames in timestamps, in milliseconds, sorted ascending with no repeats. Frames arrive at a nearly steady rate, so the timestamps are spread fairly evenly.
Write findFrame(timestamps, target) that returns the index of the frame with timestamp target, or -1 if there is none. Use the even spacing: guess the position from the value, as interpolation search does.
Input: timestamps = [0,40,80,120,160,200,240], target = 160 Output: 4
With frames every 40 ms, the first guess lands right on index 4.
Input: timestamps = [0,40,80,120,160,200,240], target = 100 Output: -1
No frame has timestamp 100.
0 <= timestamps.length <= 1000000 <= timestamps[i], target <= 10^9Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #182 Find a Frame by Timestamp. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.