8000 add binary search template · liaol/awesome-golang-leetcode@bb65a8d · GitHub
[go: up one dir, main page]
Skip to content

Commit bb65a8d

Browse files
6boris6boris
committed
add binary search template
1 parent ecf250d commit bb65a8d

File tree

2 files changed

+137
-0
lines changed

2 files changed

+137
-0
lines changed

‎lib/Search.go

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package Solution
2+
3+
// 普通搜索
4+
func BinarySearch(nums []int, target int) int {
5+
left, right := 0, len(nums)-1
6+
7+
for left < right {
8+
mid := left + (right-left)/2
9+
if nums[mid] == target {
10+
return mid
11+
} else if nums[mid] < target {
12+
left = mid + 1
13+
} else if nums[mid] > target {
14+
right = mid - 1
15+
}
16+
}
17+
18+
return -1
19+
}
20+
21+
// 左边界
22+
func BinarySearchLeftBound(nums []int, target int) int {
23+
left, right := 0, len(nums)-1
24+
25+
for left <= right {
26+
mid := left + (right-left)/2
27+
if nums[mid] == target {
28+
right = mid - 1
29+
} else if nums[mid] < target {
30+
left = mid + 1
31+
32+
} else if nums[mid] > target {
33+
right = mid - 1
34+
}
35+
}
36+
if nums[left] != target || left > len(nums) {
37+
return -1
38+
}
39+
return left
40+
}
41+
42+
// 右边界
43+
func BinarySearchRightBound(nums []int, target int) int {
44+
left, right := 0, len(nums)-1
45+
46+
for left <= right {
47+
mid := left + (right-left)/2
48+
if nums[mid] == target {
49+
left = mid + 1
50+
} else if nums[mid] < target {
51+
left = mid + 1
52+
53+
} else if nums[mid] > target {
54+
right = mid - 1
55+
}
56+
}
57+
if right < 0 || nums[right] != target {
58+
return -1
59+
}
60+
return right
61+
}

‎lib/Search_test.go

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
func TestBinarySearch(t *testing.T) {
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs []int
14+
target int
15+
expect int
16+
}{
17+
{"TestCase", []int{1, 2, 2, 2, 3}, 2, 2},
18+
}
19+
20+
// 开始测试
21+
for i, c := range cases {
22+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
23+
got := BinarySearch(c.inputs, c.target)
24+
if !reflect.DeepEqual(got, c.expect) {
25+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26+
c.expect, got, c.inputs)
27+
}
28+
})
29+
}
30+
}
31+
32+
func TestBinarySearchLeftBound(t *testing.T) {
33+
// 测试用例
34+
cases := []struct {
35+
name string
36+
inputs []int
37+
target int
38+
expect int
39+
}{
40+
{"TestCase", []int{1, 2, 2, 2, 3}, 2, 1},
41+
}
42+
43+
// 开始测试
44+
for i, c := range cases {
45+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
46+
got := BinarySearchLeftBound(c.inputs, c.target)
47+
if !reflect.DeepEqual(got, c.expect) {
48+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
49+
c.expect, got, c.inputs)
50+
}
51+
})
52+
}
53+
}
54+
55+
func TestBinarySearchRightBound(t *testing.T) {
56+
// 测试用例
57+
cases := []struct {
58+
name string
59+
inputs []int
60+
target int
61+
expect int
62+
}{
63+
{"TestCase", []int{1, 2, 2, 2, 3}, 2, 3},
64+
}
65+
66+
// 开始测试
67+
for i, c := range cases {
68+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
69+
got := BinarySearchRightBound(c.inputs, c.target)
70+
if !reflect.DeepEqual(got, c.expect) {
71+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
72+
c.expect, got, c.inputs)
73+
}
74+
})
75+
}
76+
}

0 commit comments

Comments
 (0)
0