Skip to content

Instantly share code, notes, and snippets.

@brookback
Created April 20, 2020 06:59
Show Gist options
  • Save brookback/1ff3ede2d3a91e3aa810fa58962633ec to your computer and use it in GitHub Desktop.
Save brookback/1ff3ede2d3a91e3aa810fa58962633ec to your computer and use it in GitHub Desktop.
// tslint:disable no-let
/** Return:
*
* - `< 0` if `a` comes before `b`.
* - `0` if `a` and `b` are equal.
* - `> 0` if `a` comes after `b`.
*/
type Comparator<T> = (a: T, b: T) => number;
/**
* Insert an element `t` into a **sorted** array `arr`. Does not mutate
* the array (returns a copy).
*
* This function is using Linear Search to insert the element. It'll
* give us O(n) as best case.
*
* Consider going with Binary Search if you've got huge arrays – that'll
* make it O(log n) as best case instead.
*/
export const insertInSortedArrLinear = <T>(
arr: T[],
t: T,
comp: Comparator<T>
): T[] => {
const copy = [...arr];
copy.splice(linearSearch(copy, t, comp), 0, t);
return copy;
};
const linearSearch = <T>(arr: T[], t: T, comp: Comparator<T>): number => {
// Early if pos 0 is already bigger
if (comp(arr[0], t) > 0) {
return 0;
}
if (comp(arr[arr.length - 1], t) <= 0) {
return arr.length;
}
let i = 1;
while (
i < arr.length &&
!(comp(arr[i], t) > 0 && comp(arr[i - 1], t) <= 0)
) {
i = i + 1;
}
return i;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment