mirror of https://github.com/krahets/hello-algo.git synced 2026-10-21 21:45:19 +08:00

Files

T

817a24d7ef docs(ru): polish arrays, linked lists and searching explanations (#1895 )

* placeholder

* 0413更新

* 0413删除comments

* 第四章第一节进行一对一修改，发现几个核心问题，后续不再重复叙述。具体问题参见具体说明
因为该版本不会被用在最后的校对输出中，后续不再复制纸质版原文，只标注出现不一致的部分
1.非程序部分大量出现文本和纸质版不一致，已全部修改，AI翻译版本没有纸质版自然
2.程序部分python部分就和纸质版不一致，但是其他程序和AI翻译的python一致，建议让AI先搬运纸质版python的翻译，再加工其他的部分，翻译水平尚可。
3.程序部分AI翻译版本不稳定，大部分使用动宾结构表达，少部分使用动名词结构，出现少量语法错误。纸质版大多使用动名词结构
4.相对中文在线版格式未出现问题，该部分表现较好

* 第四章后续章节未精确修改和俄语版不一致的部分，因为从第一节可以看出，AI基本上都是自己翻的。
在这里标出了所有应该修改的部分
除了第一节以外新增的问题：
1.程序部分出现语法错误
2.单复数问题在程序和标题中出现多次，正文中更是屡见不鲜
3.程序部分，python错了之后，后续的程序全部参照python一起错，建议统一修改，还是参照python但是一起修改掉

* 第十章第一节整体检查
1.正文部分和纸质版的重叠仍然基本没有，都是AI翻译
2.程序部分除了python和纸质版翻译不一致以外，出现较为严重的术语错误
3.接下来的四节内容我将不再展示正文部分的不一致，以上已经可以充分说明了

* 第十章后续章节梳理（该部分仍然绝大部分的内容都和纸质版完全不一致，从措辞到表达方法都不一致，包括正文也包括程序）
考虑到还需要进行AI设计，在此没有重复标注
其他问题：
1.正文中有一些细节，比如说引号的删除、大小写的确认、
2.程序上也出现了术语错误和语法错误

* docs(ru): refine wording after sentence-level Chinese comparison

---------

Co-authored-by: Veronica <[email protected]>
Co-authored-by: krahets <[email protected]>

2026-10-11 02:35:33 +08:00

5.0 KiB

Raw Permalink Blame History

Двоичный поиск границ

Поиск левой границы

!!! question

Дан упорядоченный массив `nums` длины $n$, который может содержать повторяющиеся элементы. Верните индекс самого левого элемента `target` в массиве. Если массив не содержит этот элемент, верните $-1$ .

Вспомним метод поиска точки вставки при двоичном поиске: после завершения поиска указатель i указывает на самый левый target , поэтому поиск точки вставки по сути является поиском индекса самого левого target.

Рассмотрим реализацию поиска левой границы через функцию поиска точки вставки. Обратите внимание: массив может не содержать target , и тогда возможны две ситуации.

Индекс точки вставки i выходит за границы массива.
Элемент nums[i] не равен target .

Если возникает любая из этих ситуаций, достаточно сразу вернуть -1 . Код приведен ниже:

[file]{binary_search_edge}-[class]{}-[func]{binary_search_left_edge}

Поиск правой границы

Как тогда найти самый правый target ? Самый прямой способ - изменить код, заменив операцию сужения указателя в случае nums[m] == target . Мы не будем приводить этот код, заинтересованные читатели могут реализовать его самостоятельно.

Ниже представлены два более изящных способа.

Повторное использование поиска левой границы

На самом деле функцию поиска самого левого элемента можно использовать и для поиска самого правого элемента. Конкретная идея такова: преобразовать поиск самого правого target в поиск самого левого target + 1.

Как показано на рисунке ниже, после завершения поиска указатель i указывает на самый левый target + 1 (если он существует), а указатель j указывает на самый правый target , поэтому достаточно вернуть $j$.

Обратите внимание: функция возвращает точку вставки i , поэтому из нее нужно вычесть 1 , чтобы получить j :

[file]{binary_search_edge}-[class]{}-[func]{binary_search_right_edge}

Преобразование в поиск элемента

Мы знаем, что если массив не содержит target , то в конце поиска указатели i и j будут указывать соответственно на первый элемент, больший target , и на самый правый элемент, меньший target .

Следовательно, как показано на рисунке ниже, для поиска левой и правой границы можно сконструировать элемент, которого нет в массиве.

Поиск самого левого target : можно преобразовать в поиск target - 0.5 и вернуть указатель i .
Поиск самого правого target : можно преобразовать в поиск target + 0.5 и вернуть указатель j .

Код здесь опущен, но стоит обратить внимание на два момента.

По условию массив не содержит дробных чисел, поэтому нам не нужно беспокоиться о том, как обрабатывать случай равенства другим элементам массива.
Поскольку этот метод вводит дробные числа, переменную target в функции нужно изменить на тип с плавающей запятой (в Python менять ничего не требуется).

5.0 KiB Raw Permalink Blame History