Задачка на сообразительность

[FINoM]

Еще одна задачка.
Есть два массива, которые генерируете вы (не суть из каких данных, главное, что вы имеете возможность создать свою структуру и тип элементов Number или String). В первом массиве содержится элемент, равный одному из элементов из второго массива. Пример:

arr1 = ['a', 'b', 'c', 'd'];
arr2 = ['e','f','g','b','h','i'];

Повторюсь, структура массива произвольная, задаваемая вами. Количество элементов массивов велико, вплоть до 1 миллиона.
Задача
Найти индексы совпадающих элементов, написав максимально оптимизированный для этой цели код и предложить структуру массива (если она отличается от указанной выше).

[Matre]

function find(A, B) {
	R = [-1, -1];
	outer: for (var i = 0; i < A.length; i++) {
		for (var j = 0; j < B.length; j++) {
			if (A[i] == B[j]) {
				R = [i, j];
				break outer;
				break;
			}
		}
	}
	return R;
}

(R[0] + 1) * (R[1] + 1) итераций.

function find(A, B) {
	var C = {}, R = [-1, -1];
	for (var i = A.length - 1; i >= 0; i--)
		C[A[i]] = i;
	for (var i = 0; i < B.length; i++) {
		if (B[i] in C) {
			R = [C[B[i]], i];
			break;
		}
	}
	return R;
}

A.length + R[1] - 1 итераций.

[Vulkan]

По первой задаче получилось немного громоздко, но работает вроде как надо:

String.prototype.index = function(sep) {
        var l = this.length, sl = sep.length - 1, i = 0, j = 0, w = '';
        while (i < l) {
            if ((this.charAt(i) == sep.charAt(0) && this.charAt(i + sl) == sep.charAt(sl)) || j != 0){
                if (j <= sl) {w += this.charAt(i + j); j++;}
                else if (j >= sl) if (w == sep) return i; else {w = ''; j = 0; i++; continue;}} else i++;}
        return -1;
    }

    var s1 = 'aababaO_o',
        s2 = 'aababababaO_o';
    l1 = 'aba', l2 = 'abac', l3 = 'aa', l4 = 'O_o', l5 = 'abaO', l6 = 'ababaO';

    alert([
        [s1.index(l1), s1.indexOf(l1)],
        [s1.index(l2), s1.indexOf(l2)],
        [s1.index(l3), s1.indexOf(l3)],
        [s1.index(l4), s1.indexOf(l4)],
        [s1.index(l5), s1.indexOf(l5)],
        [s2.index(l6), s2.indexOf(l6)]
    ].join('\n'))

[B@rmaley.e><e]

FINoM, если поддерживать отсортированность массивов (грозит вставкой за O(n), лучше использовать списки), то можно найти такую пару за O(n+m), где m и n - длины массивов.

Или использовать вместо массива какое-нибудь сбалансированное дерево. Вставка в среднем O(log n), поиск пары - O(n+m).

[B@rmaley.e><e]

Vulkan, учитывая то, что i увеличивается не на каждой итерации, этот вариант по алгоритмической сложности ничем не отличается от двух циклов.

[Matre]

***

[FINoM]

Matre, B@rmaley.e><e, даю подсказку:

Первый массив создаем "традиционно"

arr1 = {1:'a', 2:'b', 3:'c', 4:'d'};

Во втором при создании меняем ключи и значения местами

arr2 = {'e':1,'f':2,'g':3,'b':4,'h':5,'i':6};

[micscr]

arr1 = {1:'a', 2:'b', 3:'c', 4:'d'};

традиционно - специально в кавычки заключил? Как бы объект создаешь ...

[FINoM]

традиционно - специально в кавычки заключил? Как бы объект создаешь ...

Это для наглядности. На самом деле это обычный массив.