PS this is my first entry in SO, if I do something wrong, let me know and I will try to fix it. I spent almost all day trying to fix this implementation of the algorithm, and I'm at my end!
The class I am currently accepting requests 3 implementations of the same binary search algorithm in 3 significantly different languages. For one of them, I decided to go hard and shoot Erlang. Here is my code:
-export(main/1). main(_) -> io:format("Running trials... ~n", []), N = [2 bsl (2 * X + 6) || X <- lists:seq(0, 7)], lists:foreach(fun(X) -> io:format("~p: ~p ~n", [X, time_search(X)]) end, N). time_search(Size) -> A = list_to_tuple(create_list(Size)), Iterations = 2000000, time_search(A, Size + 1, 0, Iterations) / Iterations. time_search(_, _, Sum, 0) -> Sum; time_search(A, Key, Sum, IterationNum) -> Before = now(), bin_search(A, Key), time_search(A, Key, Sum + timer:now_diff(now(), Before), IterationNum - 1). create_list(Size) -> lists:seq(1, Size). bin_search(A, Key) -> bin_search(A, Key, 1, tuple_size(A)). bin_search(_, _, Lower, Upper) when Lower > Upper -> false; bin_search(A, Key, Lower, Upper) -> Mid = (Upper + Lower) div 2, Item = element(Mid, A), if Key > Item -> bin_search(A, Key, Mid + 1, Upper); Key < Item -> bin_search(A, Key, Lower, Mid - 1); true -> true end.
So this is the result:
128: 250.8094435 µs 512: 308.7264845 µs 2048: 368.5770285 µs 8192: 425.748134 µs 32768: 477.6267655 µs 131072: 533.340876 µs 524288: 601.023178 µs 2097152: 661.099404 µs
But compared to my ruby implementation, it is obviously orders of magnitude from O (lg n)
EDIT: Okay, so maybe not orders ... it seems like it's pretty logarithmic, but still seems wrong ...
Ruby:
128: 10.4756 µs 512: 11.8172 µs 2048: 13.5328 µs 8192: 15.3139 µs 32768: 17.0915 µs 131072: 18.8721 µs 524288: 21.5237 µs 2097152: 21.7187 µs
I used to use lists, but I found out that they don't have O (1) search time, so I switched to Tuples. What makes my Erlang work so inefficiently?
Just in case, here is my Ruby implementation
def p5_BinarySearch n = Array.new(8){ |i| 2 << (2 * i + 6) } n.each { |x| time = timeSearch x puts "#{x}: #{time.round 4} µs" } end def timeSearch(size) values = createArray size iterations = 2e7.to_int totalTime = 0 iterations.times{ before = Time.now binarySearch(values, size + 1) totalTime += Time.now - before } totalTime * 1e7 / iterations end def createArray(size) (1..size).to_a end def binarySearch(values, key, low = 0, high = values.length - 1) return false if low > high mid = (low + high) / 2 return binarySearch(values, key, mid + 1, high) if key > values[mid] return binarySearch(values, key, low, mid - 1) if key < values[mid] true end if __FILE__ == $0 puts "Running trials..." p5_BinarySearch end