Module: Drip::ArrayBsearch

Included in:
FakeRBTree, ImmutableDrip, SortedArray
Defined in:
lib/drip.rb

Class Method Summary collapse

Class Method Details

.lower_boundary(ary, key) ⇒ Object 



398
399
400
401
402
403
404
405
406
407
408
409
410
 
# File 'lib/drip.rb', line 398

def lower_boundary(ary, key)
  lower = -1
  upper = ary.size
  while lower + 1 != upper
    mid = (lower + upper).div(2)
    if (ary[mid][0] <=> key) < 0
      lower = mid
    else
      upper = mid
    end
  end
  return upper
end

.upper_boundary(ary, key) ⇒ Object 



412
413
414
415
416
417
418
419
420
421
422
423
424
 
# File 'lib/drip.rb', line 412

def upper_boundary(ary, key)
  lower = -1
  upper = ary.size
  while lower + 1 != upper
    mid = (lower + upper).div(2)
    if (ary[mid][0] <=> key) <= 0
      lower = mid
    else
      upper = mid
    end
  end
  return lower + 1
end