题：二分查找中，数据存在重复项，返回数据最右边的一个数据，没有找到则返回一个合理的插入位置。
package test
import (
"testing"
)
func TestSearch(t *testing.T) {
t.Log(warp([]int{1, 2, 3, 3, 5}, 3))
t.Log(warp([]int{1, 2, 3, 3, 5}, 4))
t.Log("===")
t.Log(warp([]int{3, 3, 3, 3, 3}, 3))
t.Log(warp([]int{3, 3, 3, 3, 3}, 4))
t.Log(warp([]int{3, 3, 3, 3, 3}, 2))
t.Log("===")
t.Log(warp([]int{3}, 3))
t.Log(warp([]int{3}, 2))
t.Log(warp([]int{3}, 4))
t.Log("===")
t.Log(warp([]int{}, 3))
}
func warp(arr []int, target int) (int, int) {
return search(arr, target, 0, len(arr)-1)
}
func search(arr []int, target int, start int, end int) (int, int) {
if len(arr) == 0 {
return 0, -1
}
if len(arr) == 1 {
if arr[start] == target {
return 0, 1
}
if target > arr[start] {
return start + 1, -1
}
return start, -1
}
if start < 0 || end < 0 {
return 0, -1
}
if start > len(arr)-1 || end > len(arr)-1 {
return len(arr), -1
}
if arr[start] == target {
if start+1 < len(arr) && arr[start+1] == target {
// 核心逻辑 找到需要继续往右找
return search(arr, target, start+1, end)
}
return start, 1
}
if arr[end] == target {
if end+1 < len(arr) && arr[end+1] == target {
// 核心逻辑 找到需要继续往右找
return search(arr, target, start, end+1)
}
return end, 1
}
if start == end {
if target > arr[start] {
return start + 1, -1
}
return start, -1
}
mid := start + (end-start)/2
mValue := arr[mid]
if target == mValue {
if mid+1 < len(arr) && arr[mid+1] == target {
// 核心逻辑 找到需要继续往右找
return search(arr, target, mid+1, end)
}
return mid, 1
}
if target < mValue {
// 核心逻辑 左边找
return search(arr, target, start, mid-1)
}
// 核心逻辑 右边找
return search(arr, target, mid+1, end)
}
search 返回两个值，第一个值为位置，第二个为flag，1找到，-1未找到。
核心逻辑在于找到数据时的一个处理，因为需要找到最右边的数据，所以继续向右探测一下即可。
2021年01月20日00:19:43
再三测试之后，发现
if arr[start] == target {
if start+1 < len(arr) && arr[start+1] == target {
// 核心逻辑 找到需要继续往右找
return search(arr, target, start+1, end)
}
return start, 1
}
if arr[end] == target {
if end+1 < len(arr) && arr[end+1] == target {
// 核心逻辑 找到需要继续往右找
return search(arr, target, start, end+1)
}
return end, 1
}
发现这一段完全是多余，本来想可以减少计算次数，反而失去二分的思想，画蛇添足了。
if start == end {
if target > arr[start] {
return start + 1, -1
}
return start, -1
}
这一段判断也不对，少了一个分支。
综上所述，优化了以下代码
func binarySearch(arr []int, target int) (int, int) {
if len(arr) == 0 {
return 0, -1
}
if len(arr) == 1 {
if arr[0] == target {
return 0, 1
}
if target > arr[0] {
return 1, -1
}
return 0, -1
}
return searchNew(arr, target, 0, len(arr)-1)
}
func searchNew(arr []int, target int, start int, end int) (int, int) {
if start < 0 || end < 0 {
return 0, -1
}
if start > len(arr)-1 || end > len(arr)-1 {
return len(arr), -1
}
if start == end {
if target == arr[start] {
return start, 1
}
if target > arr[start] {
return start + 1, -1
}
return start, -1
}
mid := start + (end-start)/2
mValue := arr[mid]
if target == mValue {
if mid+1 < len(arr) && arr[mid+1] == target {
// 核心逻辑 找到需要继续往右找
return searchNew(arr, target, mid+1, end)
}
return mid, 1
}
if target < mValue {
// 核心逻辑 左边找
return searchNew(arr, target, start, mid-1)
}
// 核心逻辑 右边找
return searchNew(arr, target, mid+1, end)
}
func TestSearch(t *testing.T) {
t.Log(binarySearch([]int{1, 2, 3, 3, 5}, 3))
t.Log(binarySearch([]int{1, 2, 3, 3, 5}, 4))
t.Log("===")
t.Log(binarySearch([]int{3, 3, 3, 3, 3}, 3))
t.Log(binarySearch([]int{3, 3, 3, 3, 3}, 4))
t.Log(binarySearch([]int{3, 3, 3, 3, 3}, 2))
t.Log("===")
t.Log(binarySearch([]int{3}, 3))
t.Log(binarySearch([]int{3}, 2))
t.Log(binarySearch([]int{3}, 4))
t.Log("===")
t.Log(binarySearch([]int{}, 3))
t.Log("===")
t.Log(binarySearch([]int{1, 2, 3, 3, 3, 3, 3, 3, 5}, 3))
t.Log(binarySearch([]int{3, 3, 3, 3, 4, 4}, 3))
}
顺便测试了一下两套算法的性能。
func generateArr() []int {
arr := make([]int, math.MaxInt16/2)
for i := 0; i < math.MaxInt16/2; i++ {
if i < math.MaxInt16/5 {
arr = append(arr, i)
} else if i < math.MaxInt16/4 {
arr = append(arr, math.MaxInt16/4)
} else if i < math.MaxInt16/3 {
arr = append(arr, math.MaxInt16/3)
} else {
arr = append(arr, i)
}
}
return arr
}
// var benchmarkTarget = math.MaxInt16 / 3
var benchmarkTarget = math.MaxInt16/3 + 10
func BenchmarkSearchNew(b *testing.B) {
arr := generateArr()
b.ResetTimer()
for i := 0; i < b.N; i++ {
searchNew(arr, benchmarkTarget, 0, len(arr)-1)
}
}
func BenchmarkSearchOld(b *testing.B) {
arr := generateArr()
b.ResetTimer()
for i := 0; i < b.N; i++ {
searchOld(arr, benchmarkTarget, 0, len(arr)-1)
}
}
Benchmark 结果如下：
// benchmarkTarget = math.MaxInt16/3 + 10
BenchmarkSearchNew
BenchmarkSearchNew-8 15212474 78.2 ns/op 0 B/op 0 allocs/op
BenchmarkSearchOld
BenchmarkSearchOld-8 15368810 80.2 ns/op 0 B/op 0 allocs/op
// var benchmarkTarget = math.MaxInt16 / 3
BenchmarkSearchNew
BenchmarkSearchNew-8 13529409 74.8 ns/op 0 B/op 0 allocs/op
BenchmarkSearchOld
BenchmarkSearchOld-8 71040 15132 ns/op 0 B/op 0 allocs/op
总结：对于非重复数据，两套算法性能差不多，对于重复数据，那就天差地别了，logN 还是快。
网友评论