 # 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 Design HashSet solution using TypeScript Fizz Buzz solution using TypeScript Pascal's Triangle solution using TypeScript Min Stack solution using TypeScript Symmetric Tree solution using TypeScript Same Tree solution using TypeScript