bisection

Library for searching in sorted lists and adding items while maintaining the sort order.

Port of the Python bisect with binary search functions .

If you import bisect.dart, you will get functions with names like in the Python bisect package. If you import extension.dart, you will get methods that are more consistent with Dart design standards.

package:bisection/bisect.dart	package:bisection/extension.dart
bisect(arr, x)	arr.bisectRight(x)
bisect_left(arr, x)	arr.bisectLeft(x)
bisect_right(arr, x)	arr.bisectRight(x)
insort(arr, x)	arr.insortRight(x)
insort_left(arr, x)	arr.insortLeft(x)
insort_right(arr, x)	arr.insortRight(x)
index(arr, x)	arr[arr.bsearch(x)]]
find_lt(arr, x)	arr[arr.bsearchLessThan(x)]
find_le(arr, x)	arr[arr.bsearchLessThanOrEqualTo(x)]
find_gt(arr, x)	arr[arr.bsearchGreaterThan(x)]
find_ge(arr, x)	arr[arr.bsearchGreaterThanOrEqualTo(x)]

Use bisect functions

import 'package:bisection/bisect.dart';

void main() {
  // The list must be sorted
  final arr = ['A', 'B', 'C', 'E'];

  // Find the index of an item in a sorted list
  print(bisect(arr, 'B'));  // 2

  // Find the future index for a non-existent item
  print(bisect_left(arr, 'D'));  // 3

  // Add an item to the list while keeping the list sorted
  insort(arr, 'D');
  print(arr);  // [A, B, C, D, E]

  // Locate leftmost value equal to 'C'
  print(index(arr, 'C'));  // 2

  // Find leftmost value greater than 'C'
  print(find_gt(arr, 'C'));  // D
}

Use list extensions

import 'package:bisection/extension.dart';

void main() {
  // The list must be sorted
  final arr = ['A', 'B', 'C', 'E'];

  // Find the index of an item in a sorted list
  print(arr.bisectRight('B'));  // 2

  // Find the future index for a non-existent item
  print(arr.bisectLeft('D'));  // 3

  // Add an item to the list while keeping the list sorted
  arr.insortRight('D');
  print(arr);  // [A, B, C, D, E]

  // Locate leftmost value equal to 'C'
  print(arr.bsearch('C'));  // 2

  // Locate leftmost value greater than 'C'
  print(arr.bsearchGreaterThan('C'));  // 3
}

Custom sorting

Functions bisect_* and insort_* take the key argument, similar to the argument with the same name in Python.

import 'package:bisection/bisect.dart';

void main() {
  final arr = ['zebrA', 'craB', 'coyotE'];
  // sorting by last char  
  insort(arr, 'lizarD', key: (String s) => s[s.length - 1]);
  print(arr); // [zebrA, craB, lizarD, coyotE]
}

The other functions and methods take the compare argument, a Comparator similar to the argument in List.sort.

import 'package:bisection/extension.dart';

void main() {
  final arr = ['zebrA', 'craB', 'coyotE'];

  String lastChar(String s) => s[s.length - 1];

  arr.insortRight(
      'lizarD',
      compare: (a, b) => lastChar(a).compareTo(lastChar(b)));

  print(arr); // [zebrA, craB, lizarD, coyotE]
}

Differences from Python bisect

The library is written with the intention of repeating the results of Python functions as accurately as possible. The consistency of the results is by Dart unit tests , generated by Python scripts .

The only difference is that this library does not accept negative values of the hi argument. If hi value is negative, an exception will be thrown. In the case of Python, a rather mysterious value would be returned.