Module: LilUtils::Misc::BinarySearch

Defined in:
lib/lilutils/misc/binary_search.rb

Class Method Summary collapse

Class Method Details

.in_order?(array, &block) ⇒ Boolean

Returns:

  • (Boolean) 


22
23
24
25
26
27
28
29
30
31
 
# File 'lib/lilutils/misc/binary_search.rb', line 22

def self.in_order?(array, &block)
  block = Proc.new {|x, y| x <=> y} unless block_given?
  old_order = new_order = 0
  array.each_cons(2) do |a|
    new_order = block.call(a[0], a[1])
    return false if (new_order > 0 and old_order < 0) or (new_order < 0 and old_order > 0)
    old_order = new_order if new_order != 0
  end
  true
end

.sandwiching_indexes_for(value, array, fi = 0, li = array.length-1, check_if_in_order = true) ⇒ Object 



5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
# File 'lib/lilutils/misc/binary_search.rb', line 5

def self.sandwiching_indexes_for(value, array, fi=0, li=array.length-1, check_if_in_order=true)
  # it is __not__ assumed that the array is sorted, we skip the check if we are asked to
  if check_if_in_order
    raise ArgumentError, "Unordered array provided to this routine based on binary search" unless in_order? array
  end
  # make other checks
  while true
    i = fi + (li-fi+1)/2 # Google "nearly all binary searches are broken"
    return [i, i] if array[i] == value
    return [fi, li] if (fi+1) >= li and value >= array[fi] and value <=array[li]
    return [fi-1, fi] if (fi+1) >= li and value <= array[fi]
    return [li, li+1] if (fi+1) >= li and value >= array[fi]
    value < array[i] ? li = i : fi = i
    #puts "fi=#{fi}, li=#{li}"
  end
end