未分類

Search Insert Position

Array, BinarySearch, Go, LeetCode

Search Insert Position

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.

Here are few examples.

1
2
3
4
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
提示 解題應用
Array Array/Slice
BinarySearch BinarySearch

Default:

1
2
3
func searchInsert(nums []int, target int) int {
}

解答思路:

陣列在有序排序的情況下這邊選擇最簡單的二分法來搜尋，如果有找到目標值的話就直接回傳該位置的index，如果該值不在陣列之中，此時先前二分法所找出的最後一個中間值會最接近目標值，當目標值比中間值來得大，就回傳中間值的下一個位置當插入點，反之如果比較小就回傳中間值自身的位置當插入點。

程式碼解說:

一開始便是非常標準的二分法搜尋，不斷的取出中間值與目標值做比較直到頭部的位置超過尾巴為止，當中間值小於目標值時，開頭指向的位置就改為中間index+1，而當中間值大於目標值時，尾巴指向的位置則改為中間index-1，中間值與目標值相同就直接回傳其index，最後如果目標值不在陣列之中，先前二分法所找出的最後一個中間值會最接近目標值，當目標值比中間值來得大，就回傳中間值的下一個位置當插入點，反之如果比較小就回傳中間值自身的位置當插入點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var mid int
var front int
rear := len(nums) - 1
for front <= rear {
	mid = (front + rear) / 2
	if nums[mid] < target {
		front = mid + 1
	} else if nums[mid] > target {
		rear = mid - 1
	} else {
		return mid
	}
}
if target > nums[mid] {
	return mid + 1
}
return mid

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func searchInsert(nums []int, target int) int {
	var mid int
	var front int
	rear := len(nums) - 1
	for front <= rear {
		mid = (front + rear) / 2
		if nums[mid] < target {
			front = mid + 1
		} else if nums[mid] > target {
			rear = mid - 1
		} else {
			return mid
		}
	}
	if target > nums[mid] {
		return mid + 1
	}
	return mid
}

總結:

陣列在有序排序的情況下要找特定值，有的話就回傳該值的index，沒有則回傳該值能插入有序陣列中的位置，這邊選擇最簡單的二分法來搜尋，如果有找到目標值的話就直接回傳該位置的index，如果該值不在陣列之中，此時先前二分法所找出的最後一個中間值會最接近目標值，當目標值比中間值來得大，就回傳中間值的下一個位置當插入點，反之如果比較小就回傳中間值自身的位置當插入點。

分享到