Clojure在二进制搜索结束时会抛出这个错误。为什么？如何避免呢？

Question

这是代码，它是一个直接的二进制搜索实现。

    (defn binary_search
           "searches for a single element in a sorted array in logartihmic time"
           ([array start end element]
           (do (println "start " start " end " end " middle " (int (+ (/ (- end start)        2) start))) (
           (if (= (get array  (int (+ (/ (- end start) 2) start))) element) (println "element found at " (+ (int (/ (- end start) 2)) start))
              (if (= (- end start) 0) (do (println "not found :(") -1)
                 (if (> (get array (+ (int (/ (- end start) 2)) start)) element) (binary_search array start (dec (+ (int (/ (- end start) 2)) start)) element)
                   (binary_search array (inc (+ (int (/ (- end start) 2)) start)) end element))
  )))))
  ([array element] (do (println "starting binary search....") (binary_search array 0 (dec (count array)) element)))
)

我收到的错误是在函数每次执行结束时收到的。如您所见，如果找到元素，它将输出"NullPointerException“，如果没有，则输出"ClassCastException”。

我的想法是，它试图将返回值作为一个函数来执行，而当找不到元素时，它并不是这样。

而且，当它被找到时，它不会立即返回那里的值(这是预期的)，它会尝试执行之后的语句，从而导致NPE。是那么回事吗？

=> (Clojure-First.core/binary_search [1 2 3 4 5 6 7 8] 7)
starting binary search....
start  0  end  7  middle  3
start  4  end  7  middle  5
start  6  end  7  middle  6
element found at  6
NullPointerException   Clojure-First.core/binary-search (core.clj:49)
=> (Clojure-First.core/binary_search [1 2 3 4 5 6 7 8] 8)
starting binary search....
start  0  end  7  middle  3
start  4  end  7  middle  5
start  6  end  7  middle  6
start  7  end  7  middle  7
element found at  7
NullPointerException   Clojure-First.core/binary-search (core.clj:49)
=> (Clojure-First.core/binary_search [1 2 3 4 5 6 7 8] 1)
starting binary search....
start  0  end  7  middle  3
start  0  end  2  middle  1
start  0  end  0  middle  0
element found at  0
NullPointerException   Clojure-First.core/binary-search (core.clj:49)
=> (Clojure-First.core/binary_search [1 2 3 4 5 6 7 8] 2)
starting binary search....
start  0  end  7  middle  3
start  0  end  2  middle  1
element found at  1
NullPointerException   Clojure-First.core/binary-search (core.clj:49)
=> (Clojure-First.core/binary_search [1 2 3 4 5 6 7 8] 3)
starting binary search....
start  0  end  7  middle  3
start  0  end  2  middle  1
start  2  end  2  middle  2
element found at  2
NullPointerException   Clojure-First.core/binary-search (core.clj:49)
=> (Clojure-First.core/binary_search [1 2 3 4 5 6 7 8] 17
                                     )
starting binary search....
start  0  end  7  middle  3
start  4  end  7  middle  5
start  6  end  7  middle  6
start  7  end  7  middle  7
not found :(
ClassCastException java.lang.Long cannot be cast to clojure.lang.IFn  Clojure-First.core/binary-search (core.clj:49)

Answer 1

在下面的代码摘录中：

 ...(
           (if (= (get array  (int...

您正在调用该条件的结果，就好像它是一个函数。这段代码很难读懂，但我没有看到任何迹象表明它返回了一个没有参数的函数。

PS。请尽量使用惯用的风格，特别是使用let绑定和换行符时，这段代码的可读性会更好。

简单修复方法是在挂起的左大括号处添加对println (或其他一些无关紧要的函数)的调用：

...(println
           (if (= (get array (int...

更好的做法是让Clojure代码真正具有可读性和易读性：

(defn binary-search
  "searches for a single element in a sorted array in logartihmic time"
  ([array start end element]
     (let [middle_exact (+ (/ (- end start) 2) start)
           middle (int middle_exact)
           middle-elt (get array (int middle))]
       (println "start " start " end " end " middle " middle)
       (cond 
        (= middle-elt element)
        (do (println "element found at " middle) middle)
        (or (= end middle) (= start middle))
        (do (println "not found :(") -1)
        (> middle-elt element)
        (recur array start (int (Math/floor (- end (/ middle_exact 2)))) element)
        :otherwise
        (recur array (int (Math/ceil (+ start (/ middle_exact 2)))) end element))))
  ([array element]
     (println "starting binary search....")
     (binary-search array 0 (dec (count array)) element)))

Answer 2

正如noisesmith建议的那样，NPE的原因是您试图对nil执行函数应用程序，nil是println的返回值。

我只是想整理一下代码。

(defn binary-search
  "Searches for a single element in a sorted vector in logarithmic time,
   and returns the index of the element if it exists, otherwise returns nil"
  ([v elem]
    ;(println "starting  binary search....")
    (binary-search v 0 (count v) elem))
  ([v start end elem]
    (let [index (+ start (quot (- end start) 2))]
      ;(println 'start start 'end end 'middle index)
      (if (<= start index (dec end))
        (let [mid (nth v index)]
          (cond (> mid elem) (recur v start index elem)
                (< mid elem) (recur v (inc index) end elem)
                :else index))
        nil))))

如果您想要跟踪执行，请删除注释掉的行开头的';‘。