场景概述

有N组人，人数分别为a0,a1,a2,...,aN−1a_0,a_1, a_2, ..., a_{N-1}，编号为0,1,2,...,a0−10,1,2,...,a_0-1的人在第0组，其组内编号与编号一致，编号为a0,a0+1,...,a0+a1−1a_0,a_0+1,...,a_0+a_1-1的人在第1组，其组内编号为0,1,...,a1−10,1,...,a_1-1，编号为a0+a1,a0+a1+1,a0+a1+2,...,a0+a1+a2−1a_0+a_1,a_0+a_1+1,a_0+a_1+2,...,a_0+a_1+a_2-1的人在第2组。…以此类推。

问：编号为i的人所在组号x为多少？

算法分析

由题意可设

Si=a0+a1+...+aiS_i=a_0+a_1+...+a_i

则有

第0组的人编号范围为

0≤i<S00 \leq i < S_0

第1组的人编号范围为

S0≤i<S1S_0 \leq i < S_1

第2组的人编号范围为

S1≤i<S2S_1 \leq i <S_2

则第x组的人编号范围为

Sx−1≤i<SxS_{x-1}\leq i <S_x

即我们可以先求出数组S

S0,S1,S2,...,SN−1S_0, S_1, S_2,..., S_{N-1}

通过二分查找查出比编号i大的最小值SxS_x，则x为其所在组号。i−Sx−1i-S_{x-1}为其组内编号，当x=0时，i本身即为其组内编号。

代码结构

为了使得二分查找算法的通用性，我们可抽象出可随机访问的接口定义如下，并对整形切片实现该接口，

RandomAccessible接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package binary

// RandomAccessible 可随机访问的数据接口
type RandomAccessible interface {
    Get(id int) int
    Len() int
}

type SliceAccessible struct {
    src []int
}

func (s *SliceAccessible) Get(id int) int {
    return s.src[id]
}

func (s *SliceAccessible) Len() int {
    return len(s.src)
}

SliceAccessible结构体方法测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package binary

import (
    "github.com/stretchr/testify/assert"
    "testing"
)

func TestSliceAccessible_Get(t *testing.T) {
    sa := SliceAccessible{[]int{1, 2, 3, 4}}
    assert.Equal(t, 1, sa.Get(0))
    assert.Equal(t, 4, sa.Get(3))
}

func TestSliceAccessible_Len(t *testing.T) {
    sa := SliceAccessible{[]int{1, 2, 3, 4}}
    assert.Equal(t, 4, sa.Len())

    sa = SliceAccessible{[]int{}}
    assert.Equal(t, 0, sa.Len())
}

FindFirstBigger函数

1
2
3
4
// FindFirstBigger 在一个有序表中查找比target大的最小值
func FindFirstBigger(data RandomAccessible, target int) {
    // TODO
}

遵循TDD的开发原则，该函数暂时TODO，先编写测试代码

FindFirstBigger函数测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package binary

import (
    "github.com/stretchr/testify/assert"
    "testing"
)

func TestFindFirstBigger(t *testing.T) {
    s1 := []int{1, 6, 21, 90, 100}
    // 正常情况
    assert.Equal(t, 0, FindFirstBigger(&SliceAccessible{s1}, -1))
    assert.Equal(t, 0, FindFirstBigger(&SliceAccessible{s1}, 0))

    assert.Equal(t, 1, FindFirstBigger(&SliceAccessible{s1}, 1))
    assert.Equal(t, 1, FindFirstBigger(&SliceAccessible{s1}, 4))
    assert.Equal(t, 3, FindFirstBigger(&SliceAccessible{s1}, 21))

    assert.Equal(t, 4, FindFirstBigger(&SliceAccessible{s1}, 91))
    // 比100,104大的数找不到，返回-1
    assert.Equal(t, -1, FindFirstBigger(&SliceAccessible{s1}, 100))
    assert.Equal(t, -1, FindFirstBigger(&SliceAccessible{s1}, 104))

    // 不存在任何数字，故查找到的索引值恒为-1
    assert.Equal(t, -1, FindFirstBigger(&SliceAccessible{[]int{}}, 1))
    assert.Equal(t, -1, FindFirstBigger(&SliceAccessible{[]int{}}, 4))

    s2 := []uint32{1, 3, 6}
	as2 := &SliceAccessible[uint32]{s2}
	assert.Equal(t, 1, FindFirstBigger[uint32](as2, 1))
}

算法代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package binary

// FindFirstBigger 在一个有序表中查找比target大的最小值。若找到则返回非负整数的索引值，否则返回-1
func FindFirstBigger(data RandomAccessible, target int) (id int) {
    if data.Len() == 0 {
        return -1
    }
    left := 0
    right := data.Len() - 1
    for left < right {
        mid := (right-left)/2 + left
        if data.Get(mid) > target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
if data.Get(left) <= target {
		left++
	}
	if left >= data.Len() {
		return -1
	}
    return left

之后便可直接运行单元测试文件对该算法进行测试