Бинарный поиск

@Retry32 · Регистрация: 05.05.2021

Студворк — интернет-сервис помощи студентам

Всем привет, я недавно начал изучать алгоритм бинарного поиска и совсем не могу понять как работать с upper/lower bound. Я не совсем понимаю что такое итератор, а большинство сайтов в интернете дают определение через него. Помогите пожалуйста понять в чем их разница и в каких случаях ими пользоваться?

@anton78spb · 15.07.2023, 13:24

Retry32, Вот код с Wiki из стать про "бинарный поиск".
Он очень наглядно описывает алгоритм его работы.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(list, key):
    low = 0
    high = len(list) - 1
 
    while low <= high:
        mid = (low + high) // 2
        midVal = list[mid]
        if midVal == key:
            return mid
        if midVal > key:
            high = mid - 1
        else:
            low = mid + 1
    return 'not found :('

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

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

@idealist · 15.07.2023, 16:38

Сообщение от Retry32

Я не совсем понимаю что такое итератор

Может учебник почитать?

@Semen-Semenich · 15.07.2023, 20:48

Retry32, Итераторы в Python для самых маленьких

@Retry32 · 17.07.2023, 20:53 **[ТС]**

idealist, Я пробовал, для меня все равно не совсем понятно что за объект. Может быть вы сможете посоветовать какие-то хорошие учебники где понятно все изложено?

@idealist · 17.07.2023, 21:10

Сообщение от Retry32

Может быть вы сможете посоветовать какие-то хорошие учебники где понятно все изложено?

Любой объект с методом __ next__ для перехода на следующий
результат, который генерирует исключение StopIteration при достижении конца
серии результатов, в Python считается итератором. По любому такому объекту можно также выполнять проход с помощью цикла for или другого итерационного инструмента, потому что все внутренне итерационные инструменты обычно работают,
вызывая__ next__на каждой итерации и перехватывая исключение Stopiteration
для выяснения, когда выходить. Как вскоре будет показано, для некоторых объектов
полный протокол включает дополнительный первый шаг, связанный с вызовом iter,
но для файлов он не требуется.

Это цитата из учебника Марка Лутца "Изучаем питон". Книга очень подробная и в ней он весь питон разбирает по косточкам.
А статью из четвертого сообщения не читали? Вроде толковая и доходчивая.

@Retry32 · 18.07.2023, 07:49 **[ТС]**

[/quote]

Сообщение от idealist

Это цитата из учебника Марка Лутца "Изучаем питон". Книга очень подробная и в ней он весь питон разбирает по косточкам.
А статью из четвертого сообщения не читали? Вроде толковая и доходчивая.

Я не так давно начал глубже изучать питон так что еще не успел ее прочитать, спасибо за рекомендации

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@Retry32 2 / 2 / 0 Регистрация: 05.05.2021 Сообщений: 30

	Бинарный поиск 14.07.2023, 11:09. Показов 654. Ответов 6 Метки нет (Все метки) Всем привет, я недавно начал изучать алгоритм бинарного поиска и совсем не могу понять как работать с upper/lower bound. Я не совсем понимаю что такое итератор, а большинство сайтов в интернете дают определение через него. Помогите пожалуйста понять в чем их разница и в каких случаях ими пользоваться? 0

@Semen-Semenich 5222 / 3469 / 1173 Регистрация: 21.03.2016 Сообщений: 8,295
	15.07.2023, 20:48
	Retry32, Итераторы в Python для самых маленьких 2

@Retry32 2 / 2 / 0 Регистрация: 05.05.2021 Сообщений: 30
	17.07.2023, 20:53 [ТС]
	idealist, Я пробовал, для меня все равно не совсем понятно что за объект. Может быть вы сможете посоветовать какие-то хорошие учебники где понятно все изложено? 0

Бинарный поиск

Решение