未分類

Search for a Range

Array, BinarySearch, Go, LeetCode

Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example:

1
2
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
提示 解題應用
BinarySearch BinarySearch
Array Array/Slice

Default:

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

解答思路:

如果給一排序好的陣列要找特定值，最簡單的方式就是用二分法來找出結果，但如果該陣列包含重覆值並且要給的是特定值全部出現的範圍時，此時一樣先利用二分法找出最中間的結果，接下來只要拆成兩塊分成左右兩邊，一邊是開頭到中間-1(當作新的尾巴)，另一邊則是中間+1(當作新的開頭)到尾部，先確定中間-1與中間+1兩個是否也為目標值，才再各別不斷使用二分法來漸漸一邊往左右兩邊推一邊找目標值的位置，直到開頭的位置超過中間-1與中間+1的位置超過尾巴才回傳兩邊最後分別能找出最側邊的目標值位置。

程式碼解說:

一開始先判斷傳進來的陣列是否為空，如果是就直接回傳一陣列包含兩個-1的值，而陣列不為空的話再來就是標準的二分法，不斷的找中位數並與目標值做比較，直到開頭超過尾巴的位置才結束，當中位數比目標小時，開頭就指向中間+1，而當中位數比目標大時，尾巴就指向中間-1，如果出現中位數與目標值一樣時，此時就將要回傳陣列的兩個值都改為中間值的index，並分別將中間-1當作左側的尾巴，中間+1當作右側的開頭，以利後續拆成左右兩塊各別找出最側邊的目標值位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
result := []int{-1, -1}
if len(nums) == 0 {
	return result
}
var mid int
var midFront int
var midRear 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 {
		result[0] = mid
		result[1] = mid
		midFront = mid + 1
		midRear = mid - 1
		break
	}
}

接下來先處理左側的部分，先注意到如果最右邊的值也就是尾巴(最靠近先前最中間的目標值)，如果不為目標值的話就不需要判斷了，因為其右側的所有值肯定比目標值小，而如果同為目標值才開始不斷做二分法直到開頭的位置大於新的尾巴為止，一樣從開頭與新的尾巴取中間值，如果中間值小於目標則開頭指向中間+1，不過這邊就絕對不會有中間值大於目標值的情況(因為右側最大就是尾巴的目標值)，所以再來只剩中間值是否等於目標值，是的話就將結果的第一個值改為中間值的index，並將中間-1再次作為新的尾巴以往左尋找是否還有最左邊的目標值位置

1
2
3
4
5
6
7
8
9
10
11
12
for front <= midRear && nums[midRear] == target {
	for front <= midRear {
		mid = (front + midRear) / 2
		if nums[mid] < target {
			front = mid + 1
		} else {
			result[0] = mid
			midRear = mid - 1
			break
		}
	}
}

至於右側的部分則與先一段相反，最左邊的值也就是開頭如果不為目標值的話就不需要判斷，而做二分法時也絕對不會有中間值小於目標值的情況(因為左側最小就是開頭的目標值)，其餘的部分與前一段做對照應該就相當好理解了

1
2
3
4
5
6
7
8
9
10
11
12
13
for midFront <= rear && nums[midFront] == target {
	for midFront <= rear {
		mid = (midFront + rear) / 2
		if nums[mid] > target {
			rear = mid - 1
		} else {
			result[1] = mid
			midFront = mid + 1
			break
		}
	}
}
return result

完整程式碼:

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
48
49
50
func searchRange(nums []int, target int) []int {
	result := []int{-1, -1}
	if len(nums) == 0 {
		return result
	}
	var mid int
	var midFront int
	var midRear 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 {
			result[0] = mid
			result[1] = mid
			midFront = mid + 1
			midRear = mid - 1
			break
		}
	}
	for front <= midRear && nums[midRear] == target {
		for front <= midRear {
			mid = (front + midRear) / 2
			if nums[mid] < target {
				front = mid + 1
			} else {
				result[0] = mid
				midRear = mid - 1
				break
			}
		}
	}
	for midFront <= rear && nums[midFront] == target {
		for midFront <= rear {
			mid = (midFront + rear) / 2
			if nums[mid] > target {
				rear = mid - 1
			} else {
				result[1] = mid
				midFront = mid + 1
				break
			}
		}
	}
	return result
}

總結:

一排序好的陣列包含重覆值並且要找出特定值全部出現的範圍時，此時一樣先利用二分法找出最中間的結果，接下來只要拆成兩塊分成左右兩邊，一邊是開頭到中間-1(當作新的尾巴)，另一邊則是中間+1(當作新的開頭)到尾部，先確定中間-1與中間+1兩個是否也為目標值，才再各別不斷使用二分法來漸漸一邊往左右兩邊推一邊找目標值的位置，直到開頭的位置超過中間-1與中間+1的位置超過尾巴才回傳兩邊最後分別能找出最側邊的目標值位置。

分享到