二分查找

题：二分查找中，数据存在重复项，返回数据最右边的一个数据，没有找到则返回一个合理的插入位置。

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 还是快。