未分類

Search in Rotated Sorted Array

Array, BinarySearch, Go, LeetCode

Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

提示 解題應用
BinarySearch BinarySearch
Array Array/Slice

Default:

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

解答思路:

如果一陣列是在無序的狀況下要找出特定值的話，當然就直接從頭遍歷到底即可，而如果是有序不論是從小排至大或是大排至小，都可以使用二分法甚至更細的分割演算法(插值、斐波那契等等)來找出目標，不過這題雖然看似有序但是位置卻不太正確，雖然直接以無序的方式來處理也能達到目地，不過這麼一來資料有序的部分就對我們在搜尋上一點幫助也沒有，所以倒不如找出這些有序的資料和正確位置有序相比位移了多少，接著在利用這個位移來邊做二分法等演算法就可以順利找出結果。

程式碼解說:

因要資料已經有序但位置不正確的關係，所以一開始就要先找出然正確有序相比位移了多少，而可以選擇找最小值在的位置再與index為0做相減，或是選擇找最大值再與原本最大值的index(長度-1)相減，這邊我們就以找出最小值為主，至於尋找最小值的方式也與二元搜尋脫不了關係，不過中位數比較的值是與最後一個值相比，如果中位數比最後一個值大表示最小值被移動到後頭，此時將開頭指向的index移到中位數的下一個，而如果比最後一個值小(題目有說彼此值不會重覆，故無相等情況)，就將尾巴指向的index移到中位數，記得不是移到中位數的前一個，因為我們要找的最小值也有可能是該中位數，所以也要包含在其中，最後當開頭位置超過尾巴的位置而跳開迴圈時，尾巴位置的值便是我們要的最小值

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

有了最小值的位置之後與0相減該值其實就等同於位移了多少，這時終於可以開始做二元搜尋，因為二元搜尋只關心中位數與目標值的大小比較，所以要位移的部分就只有中位數，並不需要整個陣列做位移，當找出中位數的位置而要與目標值做比較之前，要先記得暫時位移中位數到正確的位置做比較(直接將index與長度再取餘數就不需擔心index會超出範圍了)，若真正的中位數比目標值小則開頭指向中位數的下一個，而如果真正的中位數比目標值大則將尾巴指向中位數的前一個，最後如果相等便回傳真正中位數的index值，否則不存在於陣列之中回傳-1

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

完整程式碼:

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
func search(nums []int, target int) int {
	var low int
	var mid int
	var realMid int
	front := 0
	rear := len(nums) - 1
	for front < rear {
		mid = (front + rear) / 2
		if nums[mid] > nums[rear] {
			front = mid + 1
		} else {
			rear = mid
		}
	}
	low = rear
	front = 0
	rear = len(nums) - 1
	for front <= rear {
		mid = (front + rear) / 2
		realMid = (low + mid) % len(nums)
		if nums[realMid] < target {
			front = mid + 1
		} else if nums[realMid] > target {
			rear = mid - 1
		} else {
			return realMid
		}
	}
	return -1
}

總結:

陣列中資料有序但是位置卻不正確，因此要從此陣列中找出特定值的話，直接以無序的方式來處理雖然能達到目地，不過這麼一來資料有序的部分就對我們在搜尋上一點幫助也沒有，所以倒不如找出這些有序的資料和正確位置有序相比位移了多少，接著在利用這個位移來邊做二分法等演算法就可以順利找出結果。

分享到