Closest Value in a Sorted List

Given a non-empty sorted list nums and an integer target, return the element of nums whose absolute difference from target is smallest. If two elements tie, return the smaller one.

Examples

Input:  nums = [1, 4, 6, 9], target = 5
Output: 4
Explanation: 4 and 6 are both at distance 1; the smaller wins.

Input:  nums = [1, 4, 6, 9], target = 10
Output: 9

Input:  nums = [1, 4, 6, 9], target = -3
Output: 1

Constraints

• 1 <= len(nums) <= 10**6
• -10**9 <= nums[i], target <= 10**9
• O(log n) time is required.

Goals

• Locate the insertion point and inspect its two neighbours
• Break distance ties deterministically