``````

In [1]:

import (
"fmt"
"math/rand"
"sort"
)

``````
``````

In [2]:

// Return leftmost offset where val can be inserted in sl while
// maintaining sorted orter.  Assumes sl is sorted.
func bisectLeftInt(sl []int, val int) int {
return sort.Search(len(sl), func(i int) bool {return sl[i] >= val})
}

``````
``````

In [3]:

// Same but for rightmost offset
func bisectRightInt(sl []int, val int) int {
return sort.Search(len(sl), func(i int) bool {return sl[i] > val})
}

``````
``````

In [4]:

// Same as bisectLeftInt but where val and sl contain strings
func bisectLeftStr(sl []string, val string) int {
return sort.Search(len(sl), func(i int) bool {return sl[i] >= val})
}

``````
``````

In [5]:

// Same but for rightmost offset
func bisectRightStr(sl []string, val string) int {
return sort.Search(len(sl), func(i int) bool {return sl[i] > val})
}

``````
``````

In [6]:

a := []int{1, 2, 3, 3, 3, 4, 5}
bisectLeftInt(a, 3)

``````
``````

2

``````
``````

In [7]:

bisectRightInt(a, 3)

``````
``````

5

``````
``````

In [8]:

a = []int{2, 4, 6, 8, 10}
bisectLeftInt(a, 5)

``````
``````

2

``````
``````

In [9]:

bisectRightInt(a, 5)

``````
``````

2

``````
``````

In [10]:

// Make a list of pseudo-random integers in [1, 99]
rand.Seed(77)
ls := make([]int, 30)
for i := range ls {
ls[i] = rand.Intn(100) + 1
}
ls

``````
``````

[61 71 6 70 39 55 13 19 33 71 1 72 15 34 62 72 77 52 23 95 29 9 86 40 28 50 31 59 25 62]

``````
``````

In [11]:

sort.Ints(ls)
ls

``````
``````

[1 6 9 13 15 19 23 25 28 29 31 33 34 39 40 50 52 55 59 61 62 62 70 71 71 72 72 77 86 95]

``````
``````

In [12]:

// The number 30 is not in the sorted list
// If it were, where would it go?
val := 30
insPt := bisectLeftInt(ls, val)
insPt

``````
``````

10

``````
``````

In [13]:

// Insert it
ls = append(ls, 0)
copy(ls[insPt+1:], ls[insPt:])
ls[insPt] = val
ls

``````
``````

[1 6 9 13 15 19 23 25 28 29 30 31 33 34 39 40 50 52 55 59 61 62 62 70 71 71 72 72 77 86 95]

``````
``````

In [14]:

// 62 appears multiple times
st := bisectLeftInt(ls, 62)
en := bisectRightInt(ls, 62)
st

``````
``````

21

``````
``````

In [15]:

en

``````
``````

23

``````
``````

In [16]:

ls[st:en]

``````
``````

[62 62]

``````
``````

In [17]:

// Of course, there also exists a total ordering over strings
// (lexicographical ordering), so we can do all the same things
// with strings
strls := []string{"a", "awkward", "awl", "awls", "axe", "axes", "bee"}
st = bisectLeftStr(strls, "awl")
en = bisectRightStr(strls, "awl")
st

``````
``````

2

``````
``````

In [18]:

en

``````
``````

3

``````
``````

In [19]:

// Say we want to get the range of elements that have some prefix,
// e.g. 'aw' and say that 'z' is the lexicographically greatest
// character in the alphabet.
st, en = bisectLeftStr(strls, "aw"), bisectLeftStr(strls, "ax")
st

``````
``````

1

``````
``````

In [20]:

en

``````
``````

4

``````
``````

In [21]:

strls[st:en]

``````
``````

[awkward awl awls]

``````
``````

In [22]:

// If we can do this for any sorted list of strings, we can do it for
// a sorted list of suffixes
t := "abaaba\$"
suffixes := []string{t, t[1:], t[2:], t[3:], t[4:], t[5:], t[6:]}
sort.Strings(suffixes)
suffixes

``````
``````

[\$ a\$ aaba\$ aba\$ abaaba\$ ba\$ baaba\$]

``````
``````

In [23]:

// Search for suffixes starting with aba
st = bisectLeftStr(suffixes, "aba")
en = bisectLeftStr(suffixes, "abb")
st

``````
``````

3

``````
``````

In [24]:

en

``````
``````

5

``````