Binary search _ caven

binary_s.rb

require 'benchmark'

def binary_search(arr, given_element)

  length = arr.size
  t = 1                                     # search times, used to locate every step's relative_position
  relative_position = 0.5                   # compared element's relative position, initialized as 0.5 (1/2)
  current_index = (1/2.to_f * length)
  e = arr[current_index]                    # the element compared with the given_element, first time it'll be the "middle" one

  while t <= Math.log2(length).ceil         # if the given_element is not include, we only need log2(length) times search, unless we find it and break the search loop.
      if given_element < e
          t += 1
          relative_position = relative_position - 1/(2**t).to_f
          current_index =  relative_position * length
          e = arr[current_index]
      elsif given_element > e
          t += 1
          relative_position = relative_position + 1/(2**t).to_f
          current_index =  relative_position * length
          e = arr[current_index]
      elsif given_element == e
          puts "Found it ! #{t} times search.Index: --->  #{arr.index(e)}"
          break
      end
  end

  if t >= Math.log2(length).ceil && e != given_element
      puts "#{t} times search. Found nothing."
  end
end

arr = [0, 5, 13, 13, 30, 42, 52, 70, 85, 96, 103, 111, 116, 127, 130, 143, 150, 150, 161, 175, 207, 210, 218, 246, 257, 257, 263, 280, 304, 310, 326, 327, 332, 346, 360, 371, 374, 378, 406, 407, 407, 408, 428, 431, 437, 442, 445, 479, 489, 491, 505, 517, 520, 536, 548, 598, 602, 605, 618, 642, 649, 654, 659, 662, 677, 678, 682, 689, 695, 696, 697, 701, 711, 717, 727, 737, 745, 749, 754, 757, 770, 786, 802, 805, 814, 832, 840, 850, 853, 854, 888, 894, 904, 913, 913, 945, 962, 964, 972, 998]

puts "Seaching a value not present...\n"
Benchmark.bm do |x|
  x.report("arr * 1 :") {binary_search(arr, 504)}
  x.report("arr * 100 :") {binary_search(arr*100, 504)}
  x.report("arr * 10000 :") {binary_search(arr*10000, 504)}
  x.report("arr * 1000000 :"){binary_search(arr*1000000, 504)}
end

puts "\n Search 371 ..."
Benchmark.bm do |x|
  x.report("arr * 1 :") {binary_search(arr, 371)}
  x.report("arr * 100 :") {binary_search(arr*100, 371)}
  x.report("arr * 10000 :") {binary_search(arr*10000, 371)}
  x.report("arr * 1000000 :"){binary_search(arr*1000000, 371)}
end