Перейти ошибка двоичного поиска

Question

Предположим, у вас есть два варианта использования:

a := [] int {2, 2, 3, 4}
i := sort.Search(len(a), func(pos int) bool { return a[pos] == 2})
fmt.Printf("%v -> %v \n", a, i)

b := [] int {1, 2, 2, 3, 4}
j := sort.Search(len(b), func(pos int) bool { return b[pos] == 2})
fmt.Printf("%v -> %v \n", b, j)

Ответ для тех:

[2 2 3 4] -> 4
[1 2 2 3 4] -> 1

Я полагаю, это должно быть 1 в обоих случаях нет? Кто-нибудь знает почему?

Answer 1

sort.Search() возвращает наименьший индекс i в [0, n) в котором f(i) является true,

Поскольку индексы срезов основаны на 0, следует ожидать возврата 0 для первого и 1 для второго. Это (похоже) работает для второго.

Цитата из документа:

... при условии, что в диапазоне [0, n), f(i) == true подразумевает f(i+1) == true, То есть поиск требует, чтобы f является false для некоторого (возможно, пустого) префикса входного диапазона [0, n), а затем true для (возможно, пустого) остатка; Поиск возвращает первый true индекс. Если такого индекса нет, Search возвращает n,

Ваша функция не соответствует критериям sort.Search() надеется. Ваша функция состоит не в том, чтобы сказать, является ли элемент по указанному индексу тем, который вы ищете, а в том, чтобы сказать:

• если элемент по запрошенному индексу равен или больше (возврат true)
• или если элемент по указанному индексу меньше искомого (возврат false).

(Бинарный поиск не может быть выполнен, если вы скажете только, когда они равны, но не когда они больше или меньше.)

Так что просто используйте >= сравнение вместо ==, Правильное использование:

a := []int{2, 2, 3, 4}
i := sort.Search(len(a), func(pos int) bool { return a[pos] >= 2 })
fmt.Printf("%v -> %v \n", a, i)

b := []int{1, 2, 2, 3, 4}
j := sort.Search(len(b), func(pos int) bool { return b[pos] >= 2 })
fmt.Printf("%v -> %v \n", b, j)

Вывод (попробуйте на Go Playground):

[2 2 3 4] -> 0 
[1 2 2 3 4] -> 1 

Примечание: также из документа:

Например, учитывая данные среза, отсортированные в порядке возрастания, вызов

Search(len(data), func(i int) bool { return data[i] >= 23 })

возвращает наименьший индекс i такой, что data[i] >= 23, Если звонящий хочет узнать, 23 находится в срезе, его надо проверить data[i] == 23 по отдельности.

Более простая альтернатива: sort.SearchInts()

Если вы хотите найти int значение в int ломтик ([]int), просто используйте sort.SearchInts():

a := []int{2, 2, 3, 4}
i := sort.SearchInts(a, 2)
fmt.Printf("%v -> %v \n", a, i)

b := []int{1, 2, 2, 3, 4}
j := sort.SearchInts(b, 2)
fmt.Printf("%v -> %v \n", b, j)

Вывод (попробуйте на Go Playground):

[2 2 3 4] -> 0 
[1 2 2 3 4] -> 1