Practicing Our Craft
Find two bugs in the following binary search implementation:
func search(arr []int, target int) int {
l := 0
r := len(arr) - 1
for l < r {
m := (l + r) / 2
if target < arr[m] {
r = m - 1
} else {
l = m
}
}
if arr[l] == target { //assume len(arr) != 0
return l
}
return -1
}None of this is Golang specific. If you know Java, C or ( Read more... )
func search(arr []int, target int) int {
l := 0
r := len(arr) - 1
for l < r {
m := (l + r) / 2
if target < arr[m] {
r = m - 1
} else {
l = m
}
}
if arr[l] == target { //assume len(arr) != 0
return l
}
return -1
}None of this is Golang specific. If you know Java, C or ( Read more... )
Reply
Мне, однако кажется, что реалистичные ситуации, где нужен самопальный метод половинного деления таки случаются в жизни. Правда, это, скорее всего, будет не в Го.
Reply
> таки случаются в жизни
А давайте мы их придумаем.
Как насчёт Range Minimal Query, Segment Trees и Fenwick Trees? Есть либы?
Reply
Но, вообще-то мне в этом месте надо сознаваться в недостатке базового образования (или проще говоря в дремучем невежестве ; ) и лезть в Гугл.
Ну или задавать мета-вопросы типа "откуда вы всё это знаете"?
Попробую про эти вещи хотя бы в первом приближении почитать...
Reply
Мета-ответом будет "чем больше вы знаете - тем больше мест куда применить бинарный поиск (или алгебру)".
> Попробую про эти вещи хотя бы в первом приближении почитать...
Да чего там читать. Общая идея RMQ в том, чтобы "быстро" считать минимальное значение в любом куске массива. Для чего мы создаём отдельный массив в котором храним минимальное значение в каждой четвертинке массива.
Ну и если наш интервал больше четвертинки - то на большом куске нашего интервала мы уже знаем предвычисленный минимум и там поэлементно пробегать не надо.
Ну а в общем случае мы сохраняем минимум в половинках, минимум в четвертинках, в восьмушках и так далее, ну и получается минимум за log N шагов при дополнительных затратах памяти в N log N. Ну и там есть разные варианты этой идеи.
Reply
Reply
Leave a comment