Проверка входных данных по списку и добавление в список списков

Question

У меня есть неупорядоченный список, A = [1, 4, 16, 22, 9, 2] и упорядоченный список p = [0, 6, 12].

Я создал список списков s = [ [] for i in range(n+1)].

Я хочу сравнить каждый элемент A против первого элемента в p, затем второго и так далее.

Если элемент A's меньше, чем элемент p's, я хочу добавить его в правильный список в s. (таким образом, первый список в s будет пустым, так как ничто не меньше 0, второй список в s должен содержать 1,4,2. - В конечном итоге 0 войдет в первый список go, 6 во второй и 12 в третий. Четвертый список будет содержать элементы больше 12.

(мне нужно, чтобы он был обобщенным c и работал для разных размеров списка, поэтому A может содержать 20 элементов и p может удержать 5 et c ..)

Я изо всех сил пытаюсь воплотить это в жизнь. Пожалуйста, помогите!

Answer 1

Так как p отсортировано, вы можете использовать для этого bisect (со сложностью O(log(N))):

for a in A:
    s[bisect.bisect_left(p, a)].append(a)

Out:

[[], [1, 4, 2], [9], [16, 22]]