An infinite-scroll feed loads posts sorted by ID, ascending, with no repeats. The client can read feed[i] for any i, but it does not know how many posts exist: reading past the end gives undefined. Pretend you can't use feed.length.
Write searchFeed(feed, target) that returns the index of the post with ID target, or -1 if there is none. Find a range by doubling an index, then binary search inside it.
Input: feed = [2,4,7,9,13,18,21,30,35,41,50], target = 30 Output: 7
Probe 1, 2, 4, 8: feed[8] is 35, past 30. Binary search 4 to 8 finds 30 at index 7.
Input: feed = [2,4,7,9,13], target = 8 Output: -1
8 is not in the feed.
0 <= number of posts <= 1000001 <= feed[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 #180 Search an Endless Feed. 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.