Search Insert Position solution using TypeScript

Below is my TypeScript solution to the LeetCode "Search Insert Position" question using binary search.

Algorithm: Because the input is sorted, the solution uses a binary search in order to find the target value.

• It starts by creating two pointers, a left pointer at the beginning of the array and a right pointer at the end of the array.
• On each iteration, the mid-point is found between the left and right pointers, and is called a pivot.
• If the pivot is the target value, the solution has been found.
• If the pivot is greater than the target, the right pointer moves to the pivot value in order to eliminate the search space to the right.
• If the pivot is less than the target, the left pointer move to the pivot in order to eliminate the search space to the left.
• This iteration continues until a target value has been found.

Time Complexity: Because each iteration reduces the search space by half, the time complexity is O(log(n)).

Space Complexity: Because this approach uses a constant amount of space, the space complexity is O(1).

``````/**
* Search Insert Position
* Given a sorted array and a target value, return
* the index if the target is found. If not, return
* the index where it would be if it were inserted in order.
*
* Time Complexity: O(log(n))
* Space Complexity: O(1)
*
* searchInsert([1,3,5,6], 5) // 2
* searchInsert([1,3,5,6], 0) // 0
*/
function searchInsert(nums: number[], target: number): number {
let pivot;
let left = 0;
let right = nums.length - 1;

// complete a binary search
while (left <= right) {
// set pivot point half way between left and right
pivot = Math.floor((left + right) / 2);

// found target
if (nums[pivot] === target) {
return pivot;
}
// eliminate search space on the right
else if (nums[pivot] > target) {
right = pivot - 1
}
// eliminate search space on the left
else {
left = pivot + 1;
}
}
return left;
}
``````