35. Search Insert Position

---

Description

Easy
Topics
Companies
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.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4
 

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

---

Code

func searchInsert(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}

	if nums[0] > target {
		return 0
	}

	if nums[len(nums) - 1] < target {
		return len(nums)
	}

	for i := 0; i < len(nums); i++ {
		if nums[i] == target {
			return i
		}

		if nums[i] < target && nums[i + 1] > target {
			return i + 1
		}
	}

	return -1
}

 

시간 복잡도 분석

1. 초기 조건 확인:
   • len(nums) == 0 확인은 상수 시간 O(1)입니다.
   • nums[0] > target 및 nums[len(nums) - 1] < target 확인도 상수 시간 O(1)입니다.
2. 순차 탐색:
   • for i := 0; i < len(nums); i++ 반복문은 배열 nums를 한 번 순회합니다.
   • 각 반복의 내부 연산(비교 및 조건문)은 상수 시간 O(1)입니다.
   • 따라서, 반복문의 시간 복잡도는 O(n)입니다.

여기서 n은 배열 nums의 길이입니다. 따라서 전체 함수의 시간 복잡도는 O(n)입니다.