Binary search

Problem

This is how you look a word up in a paper dictionary: you open it in the middle and you already know which side to keep going. You can do that with a list that comes in already sorted.

Write a function that takes a list of numbers sorted from smallest to largest and a value, and returns the position where that value is. Positions start at 0, so in 1, 3 and 4 the number 4 is at position 2.

If the value is not in the list, you return -1. With an empty list you return -1 too.

The list always arrives sorted: you do not have to check it.

You can walk it one by one, but look at what the order gives you for free: if you look at the middle number, you know right away which half the value can be in, and you never look at the other half again.

Examples

• A single number

  [6], 6 → 0

• In the middle

  [1, 3, 4, 6, 8, 9, 11], 6 → 3

• The first one

  [1, 3, 4, 6, 8, 9, 11], 1 → 0

• The last one

  [1, 3, 4, 6, 8, 9, 11], 11 → 6

• Not there

  [1, 3, 4, 6, 8, 9, 11], 7 → -1

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

You start with this

def binary_search(nums, value):
    pass

function binarySearch(nums, value) {
}