35. Search Insert Position

Problem

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.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

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

Example 4:

Input: [1,3,5,6], 0
Output: 0

Problem Summary

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it should be inserted in order.

You may assume there are no duplicate elements in the array.

Solution Approach

• Given an array already sorted in ascending order, find the position where the target element should be inserted in the array.
• This problem is a classic variant of binary search: find the last element in the sorted array that is smaller than target.

Code

package leetcode

func searchInsert(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := low + (high-low)>>1
		if nums[mid] >= target {
			high = mid - 1
		} else {
			if (mid == len(nums)-1) || (nums[mid+1] >= target) {
				return mid + 1
			}
			low = mid + 1
		}
	}
	return 0
}