Этот стиль объявления методов очень необычен и делает ваш код трудным для чтения и понимания. Итак, мой первый шаг - воспроизвести ваш код в более идиоматической, обычной форме.
Я предпринял следующие шаги:
- ИМХО, предпочтительно, чтобы функции принимали аргументы, а не возвращали анонимные функции, принимающие аргументы. Это намного проще и чище, а ваши намерения проясняются.
- Обычно называют предикатом функции - те, которые обычно принимают один аргумент и возвращают
Boolean & mdash; p.
- В
bs переопределение аргумента функции предиката является избыточным; он может повторно использовать предикат, предоставленный для binarySearch, и поэтому не нуждается в его повторном объявлении.
- При проверке значений
Boolean принято оставлять значение обычным. То есть, если boolExpr является выражением Boolean, имеющим значение true или false, вы должны предпочесть if(boolExpr) if(boolExpr == true) и if(!boolExpr) if(boolExpr == false).
- Случай по умолчанию,
case _ может использоваться, если ни один из предыдущих случаев не совпадает. Это немного понятнее, чем case mid в вашем коде.
Ваш оригинальный код становится:
def binarySearch(p: Int => Boolean)(l: Int, h: Int): Int = {
def bs(l: Int, h: Int, minimum: Int): Int = {
val mid = l + ((h - l) / 2)
mid match {
case mid if(!p(mid)) => bs(mid+1, h, mid)
case mid if(p(mid) && mid > minimum) => bs(l, mid-1, minimum)
case mid if(p(mid) && mid < minimum) => bs(mid+1, h, mid)
case _ => mid
}
}
bs(l, h, 0)
}
ОК, теперь мы подошли к отладке вашей функции. Вы утверждаете, что он должен вычислять минимум данного интервала и что минимум должен соответствовать также данной функции . Или, другими словами, он должен найти минимальное значение в диапазоне, который удовлетворяет предикату.
Однако в вашем тестовом случае ваш предикат состоит в том, что значение должно быть меньше 5, и вы ожидаете значение 4 в качестве ответа.
Некоторые проблемы понятны:
- Ваш код предполагает, но не проверяет, что данные упорядочены от низкого до высокого. Я просто упоминаю об этом, потому что, очевидно, код потерпит неудачу, если данные не будут упорядочены. Если вы можете гарантировать, что предположение верно, то это нормально.
l, h, mid и minimum - это все индексы значений, принадлежащих Vector, которые недоступны из binarySearch - но сами они не являются значениями. Это противоречит вашему утверждению, что вы ищете минимальное значение; скорее, похоже, вы ищете index минимального значения. - В вашем тестовом условии вы ожидаете значение 4, которое является индексом значения 7. Однако 7 не соответствует предикату, так как он не меньше 5. Это наводит меня на мысль, что ваша функция предиката в вашем тесте должна быть
binarySearch(v(_) >= 5)(0, v.length).
- Вы не проверяете, что
l меньше h в binarySearch, указывая, что у вас нет диапазона для поиска. Если это происходит в bs, то вы должны рассматривать его как условие завершения (диапазон был полностью найден) и возвращать найденный индекс минимального значения. (Похоже, у вас нет такого условия завершения в существующем коде, поэтому при определенных обстоятельствах он может зацикливаться бесконечно, что в итоге приводит к StackOverflowError.)
- Следует отметить, что бинарный поиск с функцией предиката является принципиально некорректным, если только предикат не разделяет диапазон так, что индексы всех значений, которые не соответствуют предикату, являются последовательными и появляются в начале диапазона, и что индексы все значения, которые передают предикат, являются последовательными в конце диапазона. Чтобы проиллюстрировать это, рассмотрим, что произойдет, если предикат принимает только четные значения:
binarySearch(v(_) % 2 == 0)(0, v.length)? (Подсказка: ваша функция должна была бы посещать каждый элемент в диапазоне, чтобы гарантировать поиск минимума, а это не то, что делает бинарный поиск.)
- Если ваш поиск не может найти минимальное значение, которое удовлетворяет предикату, то он не может сигнализировать об этом. По этой причине я думаю, что ваша функция должна вернуть
Option[Int] со значением None, возвращаемым, если значение не может быть найдено, и Some(minimum) в противном случае. - Передача
v.length для h вызовет выброс IndexOutOfBoundsException, если будет проверено значение элемента с этим индексом. Вместо этого вы должны передать v.length - 1 или трактовать h как одну позицию за пределами диапазона.
UPDATE
Чтобы рассмотреть вашу реализацию, я немного реструктурировал проблему. Теперь функция binarySearch использует двоичный поиск, чтобы найти самое низкое значение, которое больше указанного минимума. Для этого вместо функции предиката с низким и высоким индексом она принимает IndexedSeq с именем seq и значение minimum, которое может быть принято.
// Return None if no value found, or Some(min index) otherwise.
def binarySearch(seq: IndexedSeq[Int], minimum: Int): Option[Int] = {
// Helper function. Check middle value in range. Note: h is one position beyond end of
// current range.
def bs(l: Int, h: Int, min: Option[Int]): Option[Int] = {
// If the l index isn't less than the h index, then we have nothing more to search for.
// Return whatever our current minimum is.
if(l >= h) min
// Otherwise, find the middle index value of this range.
else {
val mid = l + ((h - l) / 2)
assert(mid >= l && mid < h) // Sanity check.
// Determine if the middle value is large enough.
if(seq(mid) >= minimum) {
// OK. So this value qualifies. Update our minimum. Any potentially lower values are
// going to be in the range below mid, so look there next.
val nextMin = min.filter(_ < mid).orElse(Some(mid))
bs(l, mid, nextMin)
}
// No luck. Search the range above mid with the same minimum.
else bs(mid + 1, h, min)
}
}
// Start the search. Our initial minimum value is None.
bs(0, seq.length, None)
}
Вот несколько примеров в Scala REPL :
scala> val v = Vector(0, 1, 2, 3, 7, 9)
v: scala.collection.immutable.Vector[Int] = Vector(0, 1, 2, 3, 7, 9)
scala> binarySearch(v, 5)
res0: Option[Int] = Some(4)
scala> binarySearch(v, 9)
res1: Option[Int] = Some(5)
scala> binarySearch(v, 50)
res2: Option[Int] = None
scala> binarySearch(v, -1)
res3: Option[Int] = Some(0)