PracticeSearching

Place a Shipment by Priority

Easy/MediumSearchingbinary searchinvariantsboundary handling Time not estimated Not started

Context

A warehouse keeps shipment priority scores in nondecreasing order. When a new shipment arrives, determine where it should be inserted so that it comes after every shipment with a score no greater than its own target score. The existing score list must remain unchanged.

Problem

Given a nondecreasing array of shipment priority scores and a target score, return the first index whose score is greater than the target. If no score is greater, return the array length. Equal scores must be placed before the returned index. Use binary search so the search takes logarithmic time and constant auxiliary space. The array may be empty, contain one score, or contain repeated values.

Examples

Example 1

Input: scores = []target = 42

Output: 0

Explanation: For scores [] and target 42, execution returns 0.

Example 2

Input: scores = [10, 20, 20, 20, 35]target = 20

Output: 4

Explanation: For scores [10, 20, 20, 20, 35] and target 20, execution returns 4.

Example 3

Input: scores = [5, 12, 18, 27]target = 20

Output: 3

Explanation: For scores [5, 12, 18, 27] and target 20, execution returns 3.

Constraints

0 <= len(scores) <= 100000
-1000000000 <= scores[i] <= 1000000000 for every i
scores: sorted non decreasing
-1000000000 <= target <= 1000000000
Types: scores is int[], target is int; result is int

Function signature

def find_shipment_insertion_index(scores: list[int], target: int) -> int

scores list[int]: Nondecreasing priority scores of shipments already listed by the warehouse.
target int: Priority score of the incoming shipment.
returns int: The first index with a score greater than target, or len(scores) when every score is less than or equal to target.

Adapted from MBPP problem task_786 (CC BY 4.0). Rewritten, extended and verified by Iksha.

Code

Saved

Checking environment…Python SandboxLn 1, Col 1

scores =target =