-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathN033SearchInRotated.go
More file actions
69 lines (61 loc) · 1.36 KB
/
N033SearchInRotated.go
File metadata and controls
69 lines (61 loc) · 1.36 KB
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package main
type N033SearchInRotated struct {
}
func (this *N033SearchInRotated) binarySearch(nums []int, start int, end int, target int) int {
if start > end {
return -1
}
if target < nums[start] || target > nums[end] {
return -1
}
middle := (start + end) / 2
for start <= end {
if target == nums[middle] {
return middle
} else if target < nums[middle] {
end = middle - 1
} else {
start = middle + 1
}
middle = (start + end) / 2
}
return -1
}
func (this *N033SearchInRotated) searchInRange(nums []int, start int, end int, target int) int {
if start > end {
return -1
}
MIN_SIZE := 10
count := end - start + 1
if count <= MIN_SIZE {
for i := start; i <= end; i++ {
if nums[i] == target {
return i
}
}
return -1
}
index := -1
newEnd := (start + end) / 2
newStart := newEnd + 1
if nums[start] < nums[newEnd] {
index = this.binarySearch(nums, start, newEnd, target)
} else {
index = this.searchInRange(nums, start, newEnd, target)
}
if index >= 0 {
return index
}
if nums[newStart] < nums[end] {
index = this.searchInRange(nums, newStart, end, target)
} else {
index = this.searchInRange(nums, newStart, end, target)
}
return index
}
func (this *N033SearchInRotated) search(nums []int, numsSize int, target int) int {
if numsSize == 0 {
return -1
}
return this.searchInRange(nums, 0, numsSize-1, target)
}