noodleProblems/
Search Insert Position
#44

Search Insert Position

AlgorithmeasyArrayBinary Search

Given a sorted array of **distinct** integers nums and a target, return the index of target if it is present. If it is not, return the index where it would be inserted to keep the array sorted.

Your algorithm must run in O(log n) time.

Example cases

  • present
    in nums = [1,3,5,6], target = 5
    out 2
    5 is at index 2.
  • insert middle
    in nums = [1,3,5,6], target = 2
    out 1
    2 belongs between 1 and 3, at index 1.
  • insert end
    in nums = [1,3,5,6], target = 7
    out 4
    7 is larger than every element, so it goes at the end.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4
Saved
nums =
[1,3,5,6]
target =
5