The section a page belongs to

Problem

Clara lays out the newspaper and keeps the list of sections next to her: which page each one starts on, in order. A correction comes in for one page and she needs to know which section it belongs to, so she can tell whoever wrote it. Write a function that takes the list of pages where each section starts and a page number, and returns the position of the section that page belongs to, counting sections from 0. It is the last section whose start does not go past that page.

With the starts 1, 9, 14 and 20, page 13 is in section 1, because that section runs from page 9 to page 13. Page 9 is in section 1 too: the page a section starts on already counts as its own.

The list brings at least one start, the first one is always page 1, and the page you are asked about is always 1 or more, so there is always an answer.

You cannot use what the language already gives you to find a position (index, indexOf, findIndex, findLastIndex): the whole point of the challenge is to split the list.

Idea: look for it by halves. If the start in the middle does not go past the page, that section is a candidate: write it down and keep searching to the right, in case there is another one further along that does not go past it either. If it does go past, throw that half away.

Examples

• The correction for page 13

  [1, 9, 14, 20], 13 → 1

• The page a section starts on

  [1, 9, 14, 20], 9 → 1

• The first page

  [1, 9, 14, 20], 1 → 0

• The last section

  [1, 9, 14, 20], 25 → 3

• The page before the last start

  [1, 9, 14, 20], 19 → 2

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def section(starts, page):
    pass

function section(starts, page) {
}