Shelf Slot Finder

easy

A librarian shelves books by catalog number, ascending, no duplicates. A new book arrives. Given the sorted list shelf and the new book's number book, return the index where it belongs: its current position if the number is already shelved, otherwise the slot where inserting it keeps the shelf sorted.

O(log n), please — the shelf is long.

Example 1

in shelf = [1, 3, 5, 6], book = 5

out 2

Example 2

in shelf = [1, 3, 5, 6], book = 2

out 1

Example 3

in shelf = [1, 3, 5, 6], book = 7

out 4

Bigger than everything — goes at the end.

Constraints

· 1 <= len(shelf) <= 2000
· -10^4 <= shelf[i], book <= 10^4
· shelf is strictly increasing