# import time related routines require 'time' def binsearch(theArray, target) high = theArray.length low = -1 while (high - low > 1) probe = (high + low) / 2 if (theArray[probe] < target) low = probe else high = probe end end if (high == theArray.length || theArray[high] != target) return -1 else return high end end # Capture the current time and let the user know that # our initialization process has started now = Time.new puts "Init Start : #{now.to_s}" # create three arrays based on the value of howBig # the default value creates arrays that contain # 10_000, 50_000, and 100_000 elements # try running the program with howBig set to 1_000_000, if you want howBig = 10_000 howBig5 = howBig * 5 howBig10 = howBig * 10 a1 = [] a5 = [] a10 = [] val1 = val2 = val3 = 10 # the following loop initializes our search arrays # with a sorted set of integer values starting with the # value of 10 and increasing that value by a random number # between 1 and 10 for i in 0...howBig10 if (i < howBig) a1[i] = a5[i] = a10[i] = val1 = val3 elsif (i < howBig5) a5[i] = a10[i] = val2 = val3 else a10[i] = val3 end val3 += 1 + rand(10) end target1 = [] target2 = [] target3 = [] # the following for loop, initializes our target arrays # the last value stored in val1, val2, and val3 ensures # that we pick random numbers that have a good chance # of being in our search arrays for i in 0...10000 target1[i] = rand(val1) target2[i] = rand(val2) target3[i] = rand(val3) end # capture the current time, so we can print how long it took # to initialize the six arrays now2 = Time.new puts "Init Done : #{now2.to_s}" puts "Init Duration : #{"%3.6f" % (now2 - now)} seconds" # capture the current time, and let the user know that searching has # started now = Time.new puts "Search Start : #{now.to_s}" # invoke the searchALot method on each search array 10 times # note: we are ignoring searchALot's return value for i in 0...100 result1 = binsearch(a1, target1[i]) result2 = binsearch(a5, target2[i]) result3 = binsearch(a10, target3[i]) puts i.to_s + ": <" + result1.to_s + "," + result2.to_s + "," + result3.to_s + ">" end # capture the current time, so we can print how long it took to search # the search arrays now2 = Time.new puts "Search Done : #{now2.to_s}" puts "Search Duration : #{"%3.6f" % (now2 - now)} seconds"