使用 Go 解決 LeetCode 問題：35. Search Insert Position

Algorithm
, , ,

Description

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:
1
2
Input: [1,3,5,6], 5
Output: 2
  • Example 2:
1
2
Input: [1,3,5,6], 2
Output: 1
  • Example 3:
1
2
Input: [1,3,5,6], 7
Output: 4
  • Example 4:
1
2
Input: [1,3,5,6], 0
Output: 0

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func searchInsert(nums []int, target int) int {
	// 低點索引
	low := 0
	// 高點索引
	high := len(nums) - 1

	for low <= high {
		// 中間索引
		mid := (low + high) / 2

		if nums[mid] > target {
			// 將高點索引設置為中間索引，並減 1 避免與低點索引重疊
			high = mid - 1
		} else if nums[mid] < target {
			// 將低點索引設置為中間索引，並加 1 避免與高點索引重疊
			low = mid + 1
		} else {
			return mid
		}
	}

	return low
}

Note

假設有以下參數：

1
2
nums: [1, 3, 5, 6, 9, 13, 18, 24, 36, 45, 68, 78, 88, 95]
target: 7

說明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
第 1 次比較：

low 為 0，high 為 13，mid 為 6。

------------------------------------------------------------
 l                  m                           h
[1, 3, 5, 6, 9, 13, 18, 24, 36, 45, 68, 78, 88, 95]
------------------------------------------------------------

中間的數字為 18，大於指定值 7，所以設置 high 為 5。

第 2 次比較：

low 為 0，high 為 5，mid 為 2。

------------------------------------------------------------
 l     m        h
[1, 3, 5, 6, 9, 13, 18, 24, 36, 45, 68, 78, 88, 95]
------------------------------------------------------------

中間的數字為 5，小於指定值 7，所以設置 low 為 3。

第 3 次比較：

low 為 3，high 為 5，mid 為 4。

------------------------------------------------------------
          l  m  h
[1, 3, 5, 6, 9, 13, 18, 24, 36, 45, 68, 78, 88, 95]
------------------------------------------------------------

中間的數字為 9 大於指定值 7，所以設置 high 為 3。

第 4 次比較：

low 為 3，high 為 3，mid 為 3。

------------------------------------------------------------
          l
          m
          h
[1, 3, 5, 6, 9, 13, 18, 24, 36, 45, 68, 78, 88, 95]
------------------------------------------------------------

中間的數字為 6 小於指定值 7，所以設置 low 為 4。

最終返回：4

Code