Library for maintaining sorted Arrays
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
spec
src
.gitignore
.travis.yml
LICENSE
README.md
shard.yml

README.md

Crystal Lang Bisect

Provides helpers for dealing with sorted Arrays. It uses binary search to reduce the number of comparisons.

Build Status

Usage

There are two primary functions that you need to know about Bisect.insort and Bisect.bisect.

Bisect.insort adds a new element to the Array, but keeps the Array sorted:

require "bisect"
a = [1, 2, 4]
Bisect.insort(a, 3)
a == [1, 2, 3, 4]

Bisect.bisect gives you the index at which the element would have been inserted:

require "bisect"
a = ['a', 'b', 'd']
Bisect.bisect(a, 'c') == 2

If there are equal elements in the Array then insort will insert the element after the last equal element. Similarly bisect will return the index one higher than the last equal element. If you'd like to add new elements before equal elements, use insort_left and bisect_left. If you need to be explicit then insort_right and bisect_right are aliases for insort and bisect.

Core ext

These methods are also available directly on Arrays

require "bisect/ext"
a = [1, 2, 4]
a.insort(3)
a == [1, 2, 3, 4]