切排序的切片的最佳方法

Question

I want to cut an array of integers before a specified value, and return an array containing those values and the remaining values in the array. We can assume the array is sorted. This is what I have so far:

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
    }
}

test code:

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
", arr1, arr2, arr3)

    arr1 = []int{1,5}
    arr2, arr3 = cutIntArrBefore(arr1, 5)
    fmt.Printf("(%+v) = %+v, %+v
", arr1, arr2, arr3)

    arr1 = []int{1}
    arr2, arr3 = cutIntArrBefore(arr1, 5)
    fmt.Printf("(%+v) = %+v, %+v
", arr1, arr2, arr3)

    arr1 = []int{5}
    arr2, arr3 = cutIntArrBefore(arr1, 5)
    fmt.Printf("(%+v) = %+v, %+v
", arr1, arr2, arr3)

    arr1 = []int{5,6}
    arr2, arr3 = cutIntArrBefore(arr1, 5)
    fmt.Printf("(%+v) = %+v, %+v
", arr1, arr2, arr3)

    arr1 = []int{5,5}
    arr2, arr3 = cutIntArrBefore(arr1, 5)
    fmt.Printf("(%+v) = %+v, %+v
", arr1, arr2, arr3)

    arr1 = []int{7,7,7}
    arr2, arr3 = cutIntArrBefore(arr1, 5)
    fmt.Printf("(%+v) = %+v, %+v
", arr1, arr2, arr3)
}

output:

([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]

Unfortunately, as you can see, if the first element is after the specified value, it gets skipped over. I want to do this as elegantly as possible. I'm hoping there's another way without having to create two arrays, or adding another if statement.

Answer 1

Your implementation contains an off-by-one error, which can easily be worked around by using the index of the leftmost target value as the pivot point using the slice expressions arr[:i] and arr[i:].

Also, consider using sort.SearchInts(...) to find the target index in O(lg(n)) time instead of O(n). Using a builtin function will also likely improve legibility and maintainability of the code.

For example (Go Playground):

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]
}