lower_boundとupper_boundをGoで。

lowerBound_upperBound_test.go

package main

import (
	"fmt"
	"testing"
)

// key以上の要素のうちMINである要素の添字を返す
func lowerBound(xs []int, key int) int {
	if len(xs) == 0 {
		return 0
	}
	l, r := 0, len(xs)-1
	if xs[r] < key {
		// key以上の要素が存在しない
		return r + 1
	}
	for r-l > 1 {
		mid := l + (r-l)/2
		v := xs[mid]
		if key <= v {
			r = mid
		} else {
			l = mid
		}
	}
	if xs[l] >= key {
		return l
	}
	return r
}

// keyより大きな要素のうちMINである要素の添字を返す
func upperBound(xs []int, key int) int {
	if len(xs) == 0 {
		return 0
	}
	l, r := 0, len(xs)-1
	if xs[r] <= key {
		// keyより大きい要素が存在しない
		return r + 1
	}
	for r-l > 1 {
		mid := l + (r-l)/2
		v := xs[mid]
		if key < v {
			r = mid
		} else {
			l = mid
		}
	}
	if xs[l] > key {
		return l
	}
	return r
}

func Test_lowerBound(t *testing.T) {
	type args struct {
		xs  []int
		key int
	}
	xs := []int{2, 3, 3, 3, 5, 5, 5, 6, 7}
	tests := []struct {
		note string
		args args
		want int
	}{
		{
			args: args{xs: xs, key: 2},
			want: 0,
		},
		{
			args: args{xs: xs, key: 3},
			want: 1,
		},
		{
			args: args{xs: xs, key: 4},
			want: 4,
		},
		{
			args: args{xs: xs, key: 7},
			want: 8,
		},
		{
			note: "key以上の値が存在しない",
			args: args{xs: xs, key: 8},
			want: 9,
		},
		{
			args: args{xs: []int{}, key: 2},
			want: 0,
		},
		{
			args: args{xs: []int{3}, key: 2},
			want: 0,
		},
		{
			args: args{xs: []int{3}, key: 3},
			want: 0,
		},
		{
			args: args{xs: []int{3, 3, 3}, key: 3},
			want: 0,
		},
	}
	for _, tt := range tests {
		t.Run(fmt.Sprintf("%+v", tt.args), func(t *testing.T) {
			if got := lowerBound(tt.args.xs, tt.args.key); got != tt.want {
				t.Errorf("lowerBound() = %v, want %v", got, tt.want)
			}
		})
	}
}

func Test_upperBound(t *testing.T) {
	type args struct {
		xs  []int
		key int
	}
	xs := []int{2, 3, 3, 3, 5, 5, 5, 6, 7}
	tests := []struct {
		note string
		args args
		want int
	}{
		{
			args: args{xs: xs, key: 1},
			want: 0,
		},
		{
			args: args{xs: xs, key: 2},
			want: 1,
		},
		{
			args: args{xs: xs, key: 3},
			want: 4,
		},
		{
			args: args{xs: xs, key: 4},
			want: 4,
		},
		{
			args: args{xs: xs, key: 7},
			want: 9,
		},
		{
			args: args{xs: []int{}, key: 2},
			want: 0,
		},
		{
			args: args{xs: []int{3}, key: 2},
			want: 0,
		},
		{
			args: args{xs: []int{3}, key: 3},
			want: 1,
		},
		{
			args: args{xs: []int{3, 3, 3}, key: 2},
			want: 0,
		},
	}
	for _, tt := range tests {
		t.Run(fmt.Sprintf("%+v", tt.args), func(t *testing.T) {
			if got := upperBound(tt.args.xs, tt.args.key); got != tt.want {
				t.Errorf("upperBound() = %v, want %v", got, tt.want)
			}
		})
	}
}