Slot on a Sorted Shelf

Easy

An archive shelf holds folders whose codes are listed in the array shelf in strictly increasing order, with no repeats. A folder with code code arrives. If a folder with that code is already on the shelf, return its index. Otherwise return the index where it should be placed so the shelf stays sorted (every folder from that point on shifts one place to the right). Indices are 0-based. Your algorithm should run in O(log n) time.

Example 1

shelf=[-8, 2, 11, 30], code=11 → 2

Code 11 is already on the shelf, at position 2.

Example 2

shelf=[-8, 2, 11, 30], code=15 → 3

Code 15 is missing; to keep the order it goes between 11 and 30, which is position 3.

Example 3

shelf=[5, 9], code=-1 → 0

-1 is smaller than every code on the shelf, so its place is at the very start.

Constraints

1 ≤ shelf.length ≤ 10⁴
-10⁴ ≤ shelf[i] ≤ 10⁴
Values in shelf are distinct and sorted in ascending order
-10⁴ ≤ code ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search

Similar problems

The Lost Ticket Easy Values in Both Lists Easy Shared Values With Repeats Easy Find in a Sorted List Easy Next Letter, Wrapping Around Easy

Input

shelf=[-8, 2, 11, 30], code=11

Expected

Run checks the first 3 tests in your browser. Submit checks all 118 tests on the server, hidden ones included.