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;

more LeetCode posts