-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.go
146 lines (130 loc) · 2.83 KB
/
main.go
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
package binarysearch
import "sort"
func Search(nums []int, target int) int {
lenght := len(nums)
if lenght <= 0 {
return -1
}
left, right := 0, lenght-1
for left <= right {
mid := (right-left)/2 + left
if nums[mid] == target {
return mid
} else if nums[mid] < target {
// 找右邊
left = mid + 1
} else if nums[mid] > target {
// 找左邊
right = mid - 1
}
}
// 都沒找到
return -1
}
func Search2(nums []int, target int) int {
lenght := len(nums)
if lenght <= 0 {
return -1
}
left, right := 0, lenght-1
for left <= right {
// 除以2
// mid := left + (right-left)>>1
mid := int(uint(right+left) >> 1)
if nums[mid] == target {
return mid
} else if nums[mid] < target {
// 找右邊
left = mid + 1
} else if nums[mid] > target {
// 找左邊
right = mid - 1
}
}
// 都沒找到
return -1
}
// 內建sort
func BinarySearch(nums []int, target int) int {
length := len(nums)
index := sort.Search(length, func(i int) bool {
return nums[i] >= target
})
if index < length && nums[index] == target {
return index
} else {
return -1
}
}
// 使用遞迴
func BinarySearchRecur(nums []int, target int) (index int) {
return BinarySearchRecursively(nums, target, 0, len(nums)-1)
}
func BinarySearchRecursively(nums []int, target int, start int, end int) int {
if end < start {
return -1
}
middle := int(uint(end+start) >> 1)
if nums[middle] == target {
return middle
} else if target > nums[middle] {
return BinarySearchRecursively(nums, target, middle+1, end)
} else {
return BinarySearchRecursively(nums, target, start, middle-1)
}
}
// 有點類似 nums 小於 target的元素有幾個
func LeftBound(nums []int, target int) (index int) {
lenght := len(nums)
if lenght <= 0 {
return -1
}
left, right := 0, lenght-1
for left <= right {
// 除以2
// mid := left + (right-left)>>1
mid := int(uint(right+left) >> 1)
if nums[mid] == target {
// 要繼續找左邊, 所以把右邊變小
right = mid - 1
} else if nums[mid] < target {
// 找右邊
left = mid + 1
} else if nums[mid] > target {
// 找左邊
right = mid - 1
}
}
// 都沒找到 注意: left越界情況
if left >= lenght || nums[left] != target {
return -1
}
return left
}
func RightBound(nums []int, target int) (index int) {
lenght := len(nums)
if lenght <= 0 {
return -1
}
left, right := 0, lenght-1
for left <= right {
// 除以2
// mid := left + (right-left)>>1
mid := int(uint(right+left) >> 1)
if nums[mid] == target {
// 注意:要繼續找右邊, 所以把左邊變大=mid+1
left = mid + 1
} else if nums[mid] < target {
// 找右邊
left = mid + 1
} else if nums[mid] > target {
// 找左邊
right = mid - 1
}
}
// 都沒找到 注意:right越界情況
if right < 0 || nums[right] != target {
return -1
}
return right
}