ПОИСК В ДВУМЕРНОМ МАССИВЕ PYTHON

Поиск элемента в двумерном массиве – это распространенная задача в программировании на Python. Для ее решения можно использовать различные алгоритмы, такие как прямой перебор, бинарный поиск и т.д. Один из самых простых способов осуществить поиск – это с помощью циклов for.

array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]for i in range(len(array)):    for j in range(len(array[i])):        if array[i][j] == 5:            print("5 найдено в позиции:", i, j)

В этом примере создается двумерный массив “array” и осуществляется поиск элемента со значением 5. С помощью циклов for перебираются все индексы массива, и если найден элемент со значением 5, то выводится соответствующее сообщение.

Если массив отсортирован, более эффективным алгоритмом будет бинарный поиск, который позволит находить элемент за логарифмическое время. Для этого массив должен быть отсортирован по строкам и по столбцам.

def binary_search_2d(array, value):    low = 0    high = len(array) - 1    while low <= high:        mid = (low + high) // 2        if array[mid][0] <= value <= array[mid][-1]:            return binary_search(array[mid], value)        elif value < array[mid][0]:            high = mid - 1        else:            low = mid + 1    return -1    def binary_search(array, value):    low = 0    high = len(array) - 1    while low <= high:        mid = (low + high) // 2        if array[mid] == value:            return mid        elif value < array[mid]:            high = mid - 1        else:            low = mid + 1    return -1array = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]index = binary_search_2d(array, 5)if index != -1:    i = index // len(array)    j = index % len(array[0])    print("5 найдено в позиции:", i, j)else:    print("5 не найдено")

В этом примере реализован алгоритм бинарного поиска в отсортированном двумерном массиве “array” для поиска элемента со значением 5. Сначала осуществляется поиск строки, в которой может находиться элемент. Затем с помощью функции “binary_search” осуществляется бинарный поиск в этой строке.