-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathN035SearchInsertPos.go
More file actions
39 lines (34 loc) · 851 Bytes
/
N035SearchInsertPos.go
File metadata and controls
39 lines (34 loc) · 851 Bytes
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
package main
type N035SearchInsertPos struct {
}
func (this *N035SearchInsertPos) searchInternal(nums []int, start int, end int, target int) int {
if target <= nums[start] {
return start
}
if target > nums[end] {
return end + 1
}
COUNT_TO_SEQUENTIAL_SEARCH := 8
if end-start+1 <= COUNT_TO_SEQUENTIAL_SEARCH {
for i := start; i <= end; i++ {
if target <= nums[i] {
return i
}
}
return end + 1
}
middle := (start + end) / 2
if nums[middle] == target {
return middle
} else if nums[middle] > target {
return this.searchInternal(nums, start, middle-1, target)
} else {
return this.searchInternal(nums, middle+1, end, target)
}
}
func (this *N035SearchInsertPos) searchInsert(nums []int, numsSize int, target int) int {
if numsSize == 0 {
return 0
}
return this.searchInternal(nums, 0, numsSize-1, target)
}