The problem. Given a sorted array of distinct integers nums and a target, return the index of target if it's there. If not, return the index where it would be inserted to keep the array sorted. Your algorithm must run in O(log n) time.
nums = [1, 3, 5, 6], target = 5 -> 2
nums = [1, 3, 5, 6], target = 2 -> 1
nums = [1, 3, 5, 6], target = 7 -> 4
nums = [1, 3, 5, 6], target = 0 -> 0Found or not, the answer is the first index whose value is at least the target — the lower bound. You can find it with the lower-bound template, but there's a neat fact about the classic loop too: when it ends without finding the target, low has stopped exactly at the insert position. Every value left of low is smaller than the target and every value right of high is bigger, and the loop ends with low = high + 1, so low is the first index past all the smaller values.
function searchInsert(nums, target) { for (let i = 0; i < nums.length; i++) { if (nums[i] >= target) return i; // the first value at least the target } return nums.length; // bigger than everything: insert at the end}Time O(n), space O(1).
When the target isn't found, watch where low stops: it's the insert position.
function searchInsert(nums, target) { let low = 0; let high = nums.length - 1; while (low <= high) { const mid = low + Math.floor((high - low) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) low = mid + 1; else high = mid - 1; } return low; // left of low: all smaller; right of high: all bigger}Time O(log n), space O(1). The only change from Binary Search is the last line: return low instead of return -1.
function searchInsert(nums, target) { let low = 0, high = nums.length; // the answer can be nums.length while (low < high) { const mid = low + Math.floor((high - low) / 2); if (nums[mid] < target) low = mid + 1; else high = mid; } return low;}Time O(log n), space O(1). In an interview, mention the library call, then write the loop yourself.
nums.length, an index past the end.[1] with targets 0, 1 and 2.