关于go:Go-sortSearch和sortFind

51次阅读

共计 9201 个字符，预计需要花费 24 分钟才能阅读完成。

sort.Search()

sort.Search() 提交于边远的 2010 年 11 月 11 日, 提交者是 Go 三位创始人之一的 Robert Griesemer, 随 Go 第一个正式版本一起公布

从这个意义上说, 是规范库元老级的函数了~

sort.Search()”) 用于在排序的切片或数组中查找元素

// Search uses binary search to find and return the smallest index i
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
// f(i) == true implies f(i+1) == true. That is, Search requires that
// f is false for some (possibly empty) prefix of the input range [0, n)
// and then true for the (possibly empty) remainder; Search returns
// the first true index. If there is no such index, Search returns n.
// (Note that the "not found" return value is not -1 as in, for instance,
// strings.Index.)
// Search calls f(i) only for i in the range [0, n).
//
// A common use of Search is to find the index i for a value x in
// a sorted, indexable data structure such as an array or slice.
// In this case, the argument f, typically a closure, captures the value
// to be searched for, and how the data structure is indexed and
// ordered.
//
// For instance, given a slice data sorted in ascending order,
// the call Search(len(data), func(i int) bool {return data[i] >= 23 })
// returns the smallest index i such that data[i] >= 23. If the caller
// wants to find whether 23 is in the slice, it must test data[i] == 23
// separately.
//
// Searching data sorted in descending order would use the <=
// operator instead of the >= operator.
//
// To complete the example above, the following code tries to find the value
// x in an integer slice data sorted in ascending order:
//
//    x := 23
//    i := sort.Search(len(data), func(i int) bool {return data[i] >= x })
//    if i < len(data) && data[i] == x {//        // x is present at data[i]
//    } else {
//        // x is not present in data,
//        // but i is the index where it would be inserted.
//    }
//
// As a more whimsical example, this program guesses your number:
//
//    func GuessingGame() {
//        var s string
//        fmt.Printf("Pick an integer from 0 to 100.\n")
//        answer := sort.Search(100, func(i int) bool {//            fmt.Printf("Is your number <= %d?", i)
//            fmt.Scanf("%s", &s)
//            return s != ""&& s[0] =='y'
//        })
//        fmt.Printf("Your number is %d.\n", answer)
//    }
func Search(n int, f func(int) bool) int {// Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {h := int(uint(i+j) >> 1) // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {i = h + 1 // preserves f(i-1) == false
        } else {j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}

<font size=1 color=#00C5CD>

这段代码是一个实现了二分查找算法的函数，名为 Search。这个函数用于在一个有序的范畴内寻找满足特定条件的最小索引 i。以下是对这个函数的具体解释：

  1. 函数定义：Search(n int, f func(int) bool) int 定义了一个名为 Search 的函数，接管两个参数：一个整数 n 和一个函数 f。n 定义了搜寻范畴的大小（从 0 到 n，不包含 n），而 f 是一个承受整数输出并返回布尔值的函数。Search 函数返回一个整数，示意满足 f 条件的最小索引。
  2. 条件函数 f：f 函数定义了查找的条件。对于索引 i，如果 f(i) 为真，则对于所有 j > i，f(j) 也应为真。这意味着 f 在某点之前为假，之后变为真。Search 函数查找的是这个转变产生的点。

  3. 二分查找逻辑：

    • 初始化两个指针 i 和 j，别离代表搜寻范畴的开始和完结。开始时，i 为 0，j 为 n。
    • 在 i < j 的条件下循环执行。计算中点 h，并判断 f(h) 的值。
    • 如果 f(h) 为假（false），则阐明满足条件的索引在 h 的右侧，将 i 设置为 h + 1。
    • 如果 f(h) 为真（true），则阐明满足条件的索引可能是 h 或在 h 的左侧，将 j 设置为 h。
    • 这个过程一直放大搜寻范畴，直到找到转变点，即 f(i-1) 为假而 f(i) 为真的地位。
  4. 后果返回：当 i 与 j 相遇时，i 就是满足 f(i) 为真的最小索引。如果整个范畴内没有找到满足条件的索引，则返回 n。

这个 Search 函数的一个常见用处是在有序数组或切片中查找一个元素或查找满足某个条件的元素的插入点。例如，如果你有一个按升序排序的数组，并想要找到第一个大于等于某个值 x 的元素的索引，你能够将 x 的值和数组索引作为条件传递给 f 函数，并应用 Search 函数来查找。

这种类型的二分查找算法十分高效，工夫复杂度为 O(log n)，实用于大型数据汇合。二分查找不仅能够用于查找元素，还能够用于确定元素的插入地位，以保持数据的有序性。

</font>

会在一个已排序的切片中进行二分查找 ( 因而比线性搜寻要快得多，尤其是在解决大型数据集时性能尤其显著), 最初返回一个索引，这个索引指向切片中第一个不小于指定值的元素。如果没有找到符合条件的元素，则返回的索引等于切片的长度。

应用时首先须要确保切片或数组曾经是排序过的。其次需提供一个函数，这个函数定义了怎么判断切片中的元素是否满足自定义的查找条件。

如下, 假如有一个整数切片，曾经按升序排序，想找到第一个不小于某个给定值的元素的地位。

package main

import (
    "fmt"
    "sort"
)

func main() {
    // 已排序的切片
    numbers := []int{1, 2, 4, 6, 8, 10}

    // 要查找的值
    target := 5

    // 应用 sort.Search
    index := sort.Search(len(numbers), func(i int) bool {return numbers[i] >= target
    })

    // 输入后果
    if index < len(numbers) {fmt.Printf("找到了不小于 %d 的元素，索引为 %d，值为 %d\n", target, index, numbers[index])
    } else {fmt.Printf("没有找到不小于 %d 的元素，索引为 %d\n", target, index)
    }
}

在线运行

输入:

找到了不小于 5 的元素，索引为 3，值为 6

下面代码中,sort.Search() 用于在 numbers 切片中查找第一个不小于 5 的元素。因为 4 前面的元素是 6，所以函数返回 6 的索引，即 3。

更多例子:

Go 语言中 sort.Search()的应用办法（数组中通过值来取索引）的应用办法（数组中通过值来取索引）”)

golang 中 sort 包 sort.search()应用教程应用教程 ”)

sort.Find()

而sort.Find() 则首次提交于 2022 年 3 月 30 日, 随 2022 年 8 月 2 号公布的 Go 1.19 一起公布

// Find uses binary search to find and return the smallest index i in [0, n)
// at which cmp(i) <= 0. If there is no such index i, Find returns i = n.
// The found result is true if i < n and cmp(i) == 0.
// Find calls cmp(i) only for i in the range [0, n).
//
// To permit binary search, Find requires that cmp(i) > 0 for a leading
// prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for
// the final suffix of the range. (Each subrange could be empty.)
// The usual way to establish this condition is to interpret cmp(i)
// as a comparison of a desired target value t against entry i in an
// underlying indexed data structure x, returning <0, 0, and >0
// when t < x[i], t == x[i], and t > x[i], respectively.
//
// For example, to look for a particular string in a sorted, random-access
// list of strings:
//
//    i, found := sort.Find(x.Len(), func(i int) int {//        return strings.Compare(target, x.At(i))
//    })
//    if found {//        fmt.Printf("found %s at entry %d\n", target, i)
//    } else {//        fmt.Printf("%s not found, would insert at %d", target, i)
//    }
func Find(n int, cmp func(int) int) (i int, found bool) {
    // The invariants here are similar to the ones in Search.
    // Define cmp(-1) > 0 and cmp(n) <= 0
    // Invariant: cmp(i-1) > 0, cmp(j) <= 0
    i, j := 0, n
    for i < j {h := int(uint(i+j) >> 1) // avoid overflow when computing h
        // i ≤ h < j
        if cmp(h) > 0 {i = h + 1 // preserves cmp(i-1) > 0
        } else {j = h // preserves cmp(j) <= 0
        }
    }
    // i == j, cmp(i-1) > 0 and cmp(j) <= 0
    return i, i < n && cmp(i) == 0
}

<font size=1 color=#00C5CD>

这段代码是一个实现二分查找的算法函数，名为 Find。它的目标是在一个满足特定条件的有序汇合中查找一个元素，并返回该元素的索引和一个布尔值，示意是否找到了该元素。以下是对该函数及其组成部分的具体解释：

  1. 函数定义：Find(n int, cmp func(int) int) (i int, found bool) 定义了一个名为 Find 的函数，它承受一个整数 n 和一个比拟函数 cmp 作为参数。n 示意搜寻范畴的大小，而 cmp 是一个用于比拟元素的函数。函数返回两个值：i（找到的元素的索引）和 found（一个布尔值，示意是否找到了元素）。
  2. 比拟函数 cmp：这个函数承受一个整数索引作为输出，并返回一个整数。返回值的意义是基于目标值 t 与索引 i 处元素的比拟：如果 t 小于元素，则返回小于 0 的值；如果 t 等于元素，则返回 0；如果 t 大于元素，则返回大于 0 的值。

  3. 二分查找逻辑：

    • 初始化两个指针 i 和 j，别离指向搜寻范畴的开始和完结。i 初始化为 0，j 初始化为 n。
    • 循环执行，直到 i 不小于 j。在每次迭代中，计算中点 h，并应用 cmp 函数比拟中点处的元素。
    • 如果 cmp(h) 的后果大于 0，阐明目标值 t 在中点的右侧，因而将 i 更新为 h + 1。
    • 如果 cmp(h) 的后果不大于 0，阐明目标值 t 在中点或中点的左侧，因而将 j 更新为 h。
    • 这个过程一直放大搜寻范畴，直到 i 和 j 相遇。
  4. 后果返回：当循环完结时，i 和 j 相等。这时，如果 i 小于 n 且 cmp(i) 等于 0，则阐明找到了指标元素，函数返回 i 和 found 为 true。否则，示意没有找到指标元素，函数返回 i（此时 i 示意目标值应该插入的地位，以放弃序列的有序性）和 found 为 false。

这段代码的实用性在于，它不仅可能用于查找元素，还可能通过返回的索引 i 提供无关元素应该插入的地位的信息，这对于保护有序汇合十分有用。二分查找的效率很高，工夫复杂度为 O(log n)，实用于大型数据汇合的查找操作。

</font>

Find uses binary search to find and return the smallest index i in [0, n) at which cmp(i) <= 0. If there is no such index i, Find returns i = n. The found result is true if i < n and cmp(i) == 0. Find calls cmp(i) only for i in the range [0, n).

To permit binary search, Find requires that cmp(i) > 0 for a leading prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for the final suffix of the range. (Each subrange could be empty.) The usual way to establish this condition is to interpret cmp(i) as a comparison of a desired target value t against entry i in an underlying indexed data structure x, returning <0, 0, and >0 when t < x[i], t == x[i], and t > x[i], respectively.

Find 应用二分查找来查找并返回 [0, n) 中 cmp(i) <= 0 的最小索引 i。如果不存在这样的索引 i，Find 将返回 i = n。如果 i < n 且 cmp(i) == 0，则找到的后果为 true。Find 仅针对 [0, n) 范畴内的 i 调用 cmp(i)。

为了容许二分搜寻，Find 要求 cmp(i) > 0 作为范畴的前导前缀，cmp(i) == 0 在两头，cmp(i) < 0 作为范畴的最初后缀。（每个子范畴能够为空。）建设此条件的罕用办法是将 cmp(i) 解释为所需目标值 t 与根底索引数据结构 x 中的条目 i 的比拟，返回 <0、0 和 > 当 t < x[i]、t == x[i] 和 t > x[i] 时，别离为 0。

二者实现十分相近, 都有用二分搜寻

Find 的第二个入参, 也是一个 func, 但要求这个 func 的返回值是 int 而不是 bool. 另外 Find 的返回值有两个, 第二个返回值是 bool, 代表没有找到指定元素

sort.Find()”) 看起来和 sort.Search() 很像, 为什么有了 Search 还须要 Find? 二者有什么不同?

回溯一下 Find 的历史, 提案 sort: add Find #50340 是 Go 三位创始人之一的另一位 Rob Pike 提出

从探讨中:

It sounds like we agree that sort.Search is hard to use, but there’s not an obvious replacement. In particular, anything that can report an exact position has to take a different function (a 3-way result like strings.Compare, or multiple functions).

“ 听起来咱们都批准 sort.Search 很难应用，但没有显著的替代品。特地是，任何能够报告准确地位的货色都必须采纳不同的函数（3 路后果，如 strings.Compare 或多个函数）”

slices: add Sort, SortStable, IsSorted, BinarySearch, and func variants #47619

The difference between Search and Find in all cases would be that Find returns -1 when the element is not present,whereas Search returns the index in the slice where it would be inserted.

“ 在所有状况下，Search 和 Find 之间的区别在于，当元素不存在时，Find 返回 -1，而 Search 返回要插入元素的切片中的索引 ”

之所以 Search 大家感觉不够好用, 是因为 如果要查找的元素没在 slice 外面，Search 会返回 要插入元素的切片中的索引(并不一定是 slice 的长度, 只有当元素比切片最初一个元素还大时, 此时返回值才正好等于切片长度)，而相对不是 -1, 这样就没法判断某个元素是否在切片中, 可看上面的例子:

package main

import (
    "fmt"
    "sort"
)

func main() {data := []int{1, 2, 3, 5, 10}

    target0 := 4
    index0 := sort.Search(len(data), func(i int) bool {return data[i] >= target0
    })
    fmt.Println(index0) //3

    target1 := 5
    index1 := sort.Search(len(data), func(i int) bool {return data[i] >= target1
    })
    fmt.Println(index1) //3

    target2 := 6
    index2 := sort.Search(len(data), func(i int) bool {return data[i] >= target2
    })
    fmt.Println(index2) //4

    target3 := 11
    index3 := sort.Search(len(data), func(i int) bool {return data[i] >= target3
    })
    fmt.Println(index3) //5

}

正如 Rob Pike 所说, 他想用 sort.Search 来做搜寻, 判断某个元素是否在 (已排序的) 切片中, 但实际上, 如 target2 的 6, sort.Search()失去后果 4, 是说如果把这个元素插入这个有序切片, 须要插入在 data[4]这个地位, 并不一定是说 data[4]=6

即通过 sort.Search 无奈直接判断某个元素是否在切片中, 还须要补一个 data[index]和 target 是否相等的判断

而 Find 则不然,

package main

import (
    "fmt"
    "sort"
    "strings"
)

func main() {x := []string{"a", "e", "h", "s", "v"}

    target := "e"
    i, found := sort.Find(len(x), func(i int) int {return strings.Compare(target, x[i])
    })
    if found {fmt.Printf("found %s at entry %d\n", target, i)
    } else {fmt.Printf("%s not found, would insert at %d\n", target, i)
    }

    target2 := "g"
    j, found2 := sort.Find(len(x), func(j int) int {return strings.Compare(target2, x[j])
    })
    if found2 {fmt.Printf("found %s at entry %d\n", target2, j)
    } else {fmt.Printf("%s not found, would insert at %d\n", target2, j)
    }

}

输入:

found e at entry 1
g not found, would insert at 2

即 不光返回了应该插入到哪个地位, 还把指标元素是否在切片中也返回了~

目前 sort.Frid()没有 example, 能够把下面这段代码提交下来..

肯定水平上,Find 仿佛放在 slices 包更适合:

https://github.com/golang/go/issues/50340#issuecomment-1034071670

https://github.com/golang/go/issues/50340#issuecomment-1034341823

我批准将 sort 和 slices 包的接口解耦。前者实用于形象索引，而后者实用于理论切片

sort.Find 和 slices.BinarySearchFunc

其实, 我感觉很大水平, 是因为 slices.Contains 性能不够好 (调用了slices.Index, 即遍历检测), 而用sort.Find 前提是一个已排序的切片, 即能够用二分查找, 必定比用当初的 slices.Contains 暴力遍历要好

但其实,Contains 不须要晓得 index, 只须要晓得在不在, 有没有 … 能够思考用 map, 尽管 map 的创立等须要肯定的开销, 然而对于元素数量十分多的 case,hash 查找的 O(1)的劣势就体现进去了~ 而且不须要切片的有序的

我应该提一个提案, 来优化现有的slices.Contains

正文完
go
发表至： go
2024-02-29
 0
关于go:Golang-基础之并发知识-一
关于go:Go-快速入门指南-for
关于go:20230113-周报
关于go:基于GoGrpckubernetesIstio开发微服务的最佳实践尝试-33