Как добавить элемент в отсортированный массив?

[webgraph]

// есть отсортированный большой массив
let arr = ['ABC','BCD','CAE','CBA'];

Как добавить элемент 'BAS' сразу в нужное место, т.е. после 'ABC'?

// методы arr.push() и arr.unshift() подразумевают использование дальнейшей сортировки массива

Как добавить упорядоченно без сортировки?

[рони]

webgraph,

let arr = ['ABC', 'BCD', 'CAE', 'CBA'],
            el = 'BAS';
            len = arr.length;
            i = 0;
        for (; i < len; i++) if (el < arr[i]) break;
        arr.splice(i, 0, el);
        alert(arr)

[Aetae]

arr.splice()

Если же нужно прям оптимально и супер быстро, ту тут уж придётся бинароное дерево городить вместо массива или типа того.

[voraa]

ту тут уж придётся бинароное дерево городить вместо массива

Зачем дерево?
Бинарный поиск по отсортированному массиву.

Как то так

// ищет в отсортированном массиве arr 
// индекс первого элемента >= val 
// выдает arr.length, если все элементы < val
const findBinIndex =(arr, val) => {
	let nb=0, ne=arr.length-1;
	if (val<=arr[0]) return 0;
	if (val >= arr[ne]) return ne+1;
	let index;
	while (true) {
		index = ((ne + nb) / 2) | 0;
		if (arr[index] <= val)
			nb = index;
		else 
			ne = index;
			
		if (ne - nb == 1) {
			if (val<=arr[nb]) return nb;
			if (val >= arr[ne]) return ne+1;
			return ne;
		}
	}
}

const arr =  ['ABC', 'BCD','BCD', 'CAE', 'CBA']
let k, el;
el = 'BAS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'AAS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'CCS';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'BCD';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

el = 'CAF';
k= findBinIndex(arr, el);
arr.splice(k,0,el); 

console.log(arr)

[webgraph]

arr.splice()

Да, именно оптимально и супер быстро нужно) Можете подробнее рассказать/показать об этом бинарном древе?)

[webgraph]

Зачем дерево?
Бинарный поиск по отсортированному массиву.

А если интерполирующий?) И в чем принципиальное отличие бинарного дерева от бинарного поиска (что лучше/быстрее)?

[Aetae]

webgraph, да вон вариант от voraa оптимальный для поставленных условий.

voraa, дерево будет нужно если таких операций много - всё-таки splice сам по себе "тяжёлый".

[webgraph]

дерево будет нужно если таких операций много - всё-таки splice сам по себе "тяжёлый".

Aetae, да, операций будет много. Поэтому необходима высокая пропускная способность. Исходя из этого следует, что ваш вариант с деревом может быть более оптимальным и более быстрым. Aetae, расскажите как вы это представляете?)

[Aetae]

webgraph, массив в дерево - проводим добавления - дерево растёт - собираем в конце дерево в массив.
Конкретную реализацию писать лень, поугули.)

[webgraph]

всё-таки splice сам по себе "тяжёлый".

Если он такой "тяжёлый", то чем его заменить?