LeetCode 35: Search Insert Position Solution in Go
In this post we’ll solve and discuss the LeetCode problem no. 35 - Search Insert Position. We’ll be using Go language.
The problem has the following description:
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
As per the description the solution must have the runtime complexity of O(log n). Since the input array would be sorted and will contain distinct integers, we can use binary search to solve this.
func searchInsert(nums []int, target int) int {
// Set left and right indices for the search range.
left, right := 0, len(nums)-1
// Search while left is less than or equal to right.
for left <= right {
// Calculate the midpoint of the search range.
mid := left + (right-left)/2
// If the midpoint is equal to the target, return mid.
if nums[mid] == target {
return mid
// If the midpoint is less than the target
// then set left to mid+1 to move the
// search range's left bound to mid+1.
} else if nums[mid] < target {
left = mid + 1
// If the midpoint is greater than the target
// then set right to mid-1 to move
// the search range's right bound to mid-1.
} else {
right = mid - 1
}
}
// If the target is not found in nums
// then return left as the insertion point.
return left
}