Код к лекции 6

def binary_search(array, x): # левый бинпоиск, ищем самый левый элемент x
    # Инвариант array[left] < x == True, array[right] < x == False
    # Обращений к -1 и к len(array)-ому элементам никогда не происходит
    left, right = -1, len(array)
    while left + 1 < right:  # Заканчиваем, когда left и right идут друг за
                             # другом.
        middle = (left + right) // 2  # Никогда не равен ни left, ни right.
        if array[middle] < x:  # Сохраняем инвариант
            # 
            left = middle
        else:
            right = middle
    return right # Вернуть можно как left, так и right, в зависимости от задачи.

Пример двумерного списка:

a = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
print(a[0])
print(a[1])
print(a[0][0])
print(a[2][3])

[1, 2, 3, 4]
[5, 6, 7, 8]
1
12

print(a[5])

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-5-dcc45c5ce130> in <module>()
----> 1 print(a[5])

IndexError: list index out of range

print(a[0][100])

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-6-9aadac79de0f> in <module>()
----> 1 print(a[0][100])

IndexError: list index out of range

a = [[1], [2, 3], [4, 5, 6]]
print(a[0])
print(a[0][0])
print(a[1][1])

[1]
1
3

Вывод двумерного списка построчно и поэлементно:

a = [[1], [4, 5], [6, 7, 8]]

# вывод строк построчно
for elem in a:
    print(elem)

# вывод элементов построчно
for i in range(len(a)):
    for j in range(len(a[i])):
        # длина каждой строки может быть разной
        print(a[i][j], end=' ')
    print()
    # без параметров просто выводит перевод строки

for elem in a:
    for j in range(len(elem)):
        print(elem[j], end=' ')
    print()

[1]
[4, 5]
[6, 7, 8]
1 
4 5 
6 7 8 
1 
4 5 
6 7 8 

Неправильная инициализация двумерного массива нулями и последствия:

n, m = [int(i) for i in input().split()]
bad = [[0] * m] * n
print(bad)

4 5
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

bad[0][0] = 1
print(bad)
print(id(bad[0]), id(bad[1])) # id возвращает номер объекта в памяти.

[[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]]
140527377284360 140527377284360

Правильный вариант инициализации двумерного массива нулями:

good = [[0] * m for i in range(n)]
good[0][0] = 1
print(good)
print(id(good[0]), id(good[1]))

[[1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
140527377396424 140527377396808

Операторы is и is not: a is b проверяет, ссылаются ли a и b на один и от же объект

print(bad[0] is bad[1])
print(good[0] is good[1])
print(good[0] is not good[1])

True
False
True

Считывание двумерного списка c клавиатуры:

a = []
n, m = [int(i) for i in input().split()]
for i in range(n):
    a.append([int(i) for i in input().split()])
print(a)

2 3
1 2 3
4 5 6
[[1, 2, 3], [4, 5, 6]]

Считывание двумерного списка из файла:

fin = open("input.txt", "r")
n, m = [int(i) for i in fin.readline().split()]
a = []
for i in range(n):
    a.append([int(i) for i in fin.readline().split()])