Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- require 'benchmark'
- def binary_search(arr, element)
- index = nil
- first = 0
- last = arr.size-1
- while first <= last
- medium = (last + first)/2
- if arr[medium] < element
- first = medium + 1
- elsif arr[medium] > element
- last = medium - 1
- else
- index = medium
- break
- end
- end
- return index
- 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]
- p binary_search(arr, 371)
- a1 = Array.new(10){ rand(1000) }.sort
- a2 = Array.new(100){ rand(1000) }.sort
- a3 = Array.new(1000){ rand(1000) }.sort
- a4 = Array.new(1000000){ rand(1000) }.sort
- Benchmark.bm do |x|
- x.report {
- binary_search(a1, 371)
- }
- x.report {
- binary_search(a2, 371)
- }
- x.report {
- binary_search(a3, 371)
- }
- x.report {
- binary_search(a4, 371)
- }
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement