/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
matrix/binary_search_matrix.py
57 строк
2 KB
Anurag Shukla
Create binary_search_matrix.py (#6995)
13 окт 2022, 23:03
Не верифицирован
13 окт 2022, 23:03
3deb4a3
Код
Авторство
О чём код?
def binary_search(array: list, lower_bound: int, upper_bound: int, value: int) -> int: """ This function carries out Binary search on a 1d array and return -1 if it do not exist array: A 1d sorted array value : the value meant to be searched >>> matrix = [1, 4, 7, 11, 15] >>> binary_search(matrix, 0, len(matrix) - 1, 1) 0 >>> binary_search(matrix, 0, len(matrix) - 1, 23) -1 """ r = int((lower_bound + upper_bound) // 2) if array[r] == value: return r if lower_bound >= upper_bound: return -1 if array[r] < value: return binary_search(array, r + 1, upper_bound, value) else: return binary_search(array, lower_bound, r - 1, value) def mat_bin_search(value: int, matrix: list) -> list: """ This function loops over a 2d matrix and calls binarySearch on the selected 1d array and returns [-1, -1] is it do not exist value : value meant to be searched matrix = a sorted 2d matrix >>> matrix = [[1, 4, 7, 11, 15], ... [2, 5, 8, 12, 19], ... [3, 6, 9, 16, 22], ... [10, 13, 14, 17, 24], ... [18, 21, 23, 26, 30]] >>> target = 1 >>> mat_bin_search(target, matrix) [0, 0] >>> target = 34 >>> mat_bin_search(target, matrix) [-1, -1] """ index = 0 if matrix[index][0] == value: return [index, 0] while index < len(matrix) and matrix[index][0] < value: r = binary_search(matrix[index], 0, len(matrix[index]) - 1, value) if r != -1: return [index, r] index += 1 return [-1, -1] if __name__ == "__main__": import doctest doctest.testmod()