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 



376
377
378
379
380
381
382
383
384
385
386
387
388
 
# File 'lib/drip.rb', line 376

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 



390
391
392
393
394
395
396
397
398
399
400
401
402
 
# File 'lib/drip.rb', line 390

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