#160EasyBinary Search· Insertion Point

Sorted Slot Finder

A library shelves its books in increasing order of catalogue number, and the numbers on the shelf are all different. A new book arrives with catalogue number `target`. The librarian wants the shelf position (0-based) where the book belongs: if a book with that number is already there, its position; otherwise the position where the new book would be inserted so that the shelf stays sorted. Given the sorted array `shelf` and an integer `target`, return that index. The shelf can hold up to a hundred thousand books, so the answer must be found in O(log n) time.

Input format

`shelf`: a strictly increasing array of integers; `target`: an integer.

Output format

An integer index between 0 and `shelf.length` inclusive.

Examples

Input: shelf = [1, 3, 5, 6], target = 5

Output: 2

The value 5 is already on the shelf at index 2.

Input: shelf = [1, 3, 5, 6], target = 2

Output: 1

2 is missing; inserting it at index 1 keeps the order 1, 2, 3, 5, 6.

Input: shelf = [1, 3, 5, 6], target = 7

Output: 4

7 is larger than everything, so it goes at the end, index 4 (the length of the shelf).

Constraints

1 <= shelf.length <= 10^5
-10^9 <= shelf[i] <= 10^9
`shelf` is sorted in strictly increasing order.
-10^9 <= target <= 10^9

#binary-search
#arrays
#sorted-array