Search insert position

Leetcode 35 problem.

A function, given a sorted array of distinct integers 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.

Go

Time complexity: $O(n)$ - n is a length of an array
Auxiliary space: $O(1)$ - constant amount of space

func searchInsert(nums []int, target int) int {
    for index, number := range nums {
        // 1. equal number
        // 2. since array is sorted, first larger number has position of possible insert

        if number == target || number > target {
            return index
        }
    }

    // if there is no such a number and none of the numbers is larger than parameter number
    // return new last index
    return len(nums)
}

Typescript

Time complexity: $O(n)$ - n is a length of an array
Auxiliary space: $O(1)$ - constant amount of space

function searchInsert(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    // 1. equal number
    // 2. since array is sorted, first larger number has position of possible insert

    if (nums[i] == target || nums[i] > target) {
      return i;
    }
  }

  // if there is no such a number and none of the numbers is larger than parameter number
  // return new last index
  return nums.length;
}

thoughtbook

Search insert position

Go

Typescript