切割排序切片的最佳方法

Question

我想在指定值之前剪切一个整数数组，并返回一个包含这些值和数组中剩余值的数组。我们可以假设数组已排序。这是我到目前为止所拥有的：

func cutIntArrBefore(arr1 []int, n int) ([]int, []int) {

    arr2 := make([]int, 0, len(arr1))

    sliceIndex := 0

    for i, num := range arr1 {

        if num < n {

            arr2 = append(arr2, num)

            sliceIndex = i

        }

    }

    sliceIndex = sliceIndex + 1

    if sliceIndex >= len(arr1) {

        return arr2, nil

    } else {

        arr1 := arr1[sliceIndex:]   

        return arr2, arr1

    }

}

测试代码：

func main() {

    var arr1, arr2, arr3 []int

    arr1 = []int{1,2,3,4,5,6,7,8}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

    arr1 = []int{1,5}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

    arr1 = []int{1}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

    arr1 = []int{5}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

    arr1 = []int{5,6}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

    arr1 = []int{5,5}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

    arr1 = []int{7,7,7}

    arr2, arr3 = cutIntArrBefore(arr1, 5)

    fmt.Printf("(%+v) = %+v, %+v\n", arr1, arr2, arr3)

}

输出：

([1 2 3 4 5 6 7 8]) = [1 2 3 4], [5 6 7 8]

([1 5]) = [1], [5]

([1]) = [1], []

([5]) = [], []

([5 6]) = [], [6]

([5 5]) = [], [5]

([7 7 7]) = [], [7 7]

不幸的是，如您所见，如果第一个元素在指定值之后，它将被跳过。我想尽可能优雅地做到这一点。我希望有另一种方法，而不必创建两个数组或添加另一个 if 语句。

Answer 1

arr[:i]您的实现包含一个差一错误，可以通过使用切片表达式和将最左边的目标值的索引作为轴心点轻松解决arr[i:]。另外，考虑使用sort.SearchInts(...)to find the target index in O(lg(n))time 而不是O(n). 使用内置函数也可能会提高代码的易读性和可维护性。例如（去游乐场）：func cutBefore(xs []int, x int) ([]int, []int) {  i := sort.SearchInts(xs, x)  return xs[:i], xs[i:]}func main() {  xss := [][]int{    {1, 2, 3, 4, 5, 6, 7, 8},    {1, 5},    {1},    {5},    {5, 6},    {5, 5},    {7, 7, 7},  }  for _, xs := range xss {    fmt.Println(cutBefore(xs, 5))  }  // [1 2 3 4] [5 6 7 8]  // [1] [5]  // [1] []  // [] [5]  // [] [5 6]  // [] [5 5]  // [] [7 7 7]}