Поиск в последовательности: линейный, двоичный, интерполяционный, границы диапазона — авторское изложение

ru · official · sha256:82cccb94ce4f500dc6795e9825ca5fa68bb862fd1f1efc709ff4d72b5492491bRU

§1. Последовательность, порядок и полуинтервал поиска Последовательность длины n есть отображение позиций 0, 1, …, n − 1 в элементы. Обращение к элементу по позиции считается неделимой операцией; последовательность, у которой такого обращения нет, требует другого описания поиска. Последовательность упорядочена неубывающе, когда для любых позиций i < j выполнено a[i] ≤ a[j]. Упорядоченность есть предусловие, а не свойство, проверяемое алгоритмом: двоичный поиск, запущенный на неупорядоченном входе, не «работает медленнее» — он не определён. Полуинтервал поиска [lo, hi) — пара позиций, обозначающая рассматриваемый участок: левая граница включается, правая нет. Пустой полуинтервал есть тот, у которого lo равно hi. Полуинтервальная запись выбрана изложением намеренно: она избавляет от отдельного разбора однопозиционного участка и делает длину участка равной hi − lo без поправок. Середина полуинтервала вычисляется как lo + (hi − lo) / 2 нацело. Форма (lo + hi) / 2 даёт то же значение математически, но переполняется на больших позициях в машинной арифметике фиксированной разрядности; это расхождение названо здесь потому, что оно и есть содержание известной поправки к двоичному поиску. Первая позиция диапазона равных элементов — наименьшая позиция, в которой стоит искомое значение; она же есть наименьшая позиция, в которой стоит значение, не меньшее искомого. Последняя позиция диапазона — наибольшая позиция с искомым значением; описания ниже выдают позицию, СЛЕДУЮЩУЮ за ней, то есть наименьшую позицию со значением, строго большим искомого. Обе величины определены и тогда, когда искомого значения в последовательности нет; именно поэтому они говорят больше, чем «нашлось или нет». Инвариант границ — утверждение о том, что искомое, если оно есть, лежит в текущем полуинтервале. Он общий у всех трёх поисков по упорядоченному входу и объясняет, почему сужение границ не теряет ответа.

Referencing norms: AnswersHere, f-00da716ed02e2a06b73e3eb4, f-03153230076155e6b8d8f57c, f-07b2e6e2f9242cc6870bfabf, f-0fb938869b28331ee38361a5, f-0ff65e1c93d37011e1a9b6b5, f-1e1c1547d2bef4c636968837, f-1ffc4ad1aca5e8baf2712d4f, f-24570fa3b7cd1bac087224ad, f-2475965a4304d3b612a144dd, f-25500618bee58e308f9210d8, f-2eb048e62694896925a86650, f-331d103ec360ee5d7ea6edad, f-3768fd237b15d6c3603cc271, f-3b7114c292dec8f70a9559e3, f-3c0e0e83ea1994920fd3cf5f, f-3ffa6c1a08822bf722f9849b, f-48c9dece4ee78263d0c42474, f-4d66dc2c34c3e7218be22f9a, f-57aa14b7df9bb45aa6e575d5, f-5b638445f72910502ea94bad, f-5d7a1307c97c6cc4cd3bf50e, f-674311bd718a56b1e19c4b55, f-69f86138460b704821842bd8, f-76afb9cad6ad8b86f9eb7943, f-78517cca772006bdc05e1701, f-7f29909e67ea0f0a0e38a15d, f-7fc261aef53f302694b68894, f-83c00eb43994e4cf2c62231c, f-969717cd760818baa9362311, f-9fac59d701327dbe97fca227, f-a2326346e4dbe97d4df3638e, f-b76bc93b67173a9fdea11b07, f-be263c7cee3710ad86d9171a, f-bf2a7eff00d066e91ca87317, f-d280f0899e1ac8d75ca64f4b, f-d2b3e8abf97a1b28bcf029e9, f-daf3cba8bf9dc0ee775bce83, f-e52c557942b060aea732e336, f-e731bcd8447ec22803c5a7b8, f-f08bfa17e002bb4a6f0b74a6, f-f3a5fe571f830776a730bed0, f-f62ff3e878768d8ac9335821, f-f97583b73dfec32a4328f123

ru · official · sha256:d44533d24b0f01080ff02728d619778b54413a4426189816292a34d4dbe181a9RU

§2. Линейный поиск Задача: по последовательности и искомому значению получить позицию его первого вхождения либо признак отсутствия. Вариант — просмотр позиций слева направо с остановкой на первом совпадении. Позиция начинается с нуля и увеличивается на единицу, пока не исчерпаны элементы. На каждом шаге текущий элемент сравнивается с искомым; при совпадении описание выдаёт текущую позицию. По исчерпании последовательности выдаётся признак отсутствия. Упорядоченность НЕ требуется, и это главное свойство варианта: линейный поиск есть единственный из пяти, применимый к произвольной последовательности. Он же единственный, применимый к потоку, у которого обращения по позиции нет вовсе. Инвариант: перед каждой проверкой все позиции, меньшие текущей, содержат значения, отличные от искомого. Мера убывания — число непросмотренных позиций. Оценка: в худшем случае n сравнений, в среднем — около половины n при равновероятном положении искомого; оценка среднего случая опирается на предположение о распределении и без него смысла не имеет.

Referencing norms: f-01c497b3a94ae0e22af9f7be, f-04dc435f4fd1db5d6bafbea0, f-0dfbd8abd0d614401a25272e, f-13a29ec7f473f47abf530ed9, f-1409bed96aa34366fb73e8ef, f-16b9cb5fa00314035fdc1df3, f-18bb674f291dcd2bb00728cd, f-1b5310d782a6fa7b23c61b26, f-1bc6794c7e4b5d3ad4de5910, f-1f05fcc10f5847df1bf92351, f-256721c4da2526303504128b, f-29f7c7398dda2e8ab78f95d4, f-2dd903e739a14f8799bc62f8, f-2e7090d25fcea8bdb65ba166, f-338bc1b2af20f45bced7ae6e, f-3547a7ec5c85192d427d0ab6, f-37639230b5780d8eeb66e4f5, f-403abd192ec6241634bddc8d, f-409185828c142cba08a4bb3a, f-43ba67421f8e713fec7e0bc7, f-440064a07abf296c1d1675ff, f-471296e3557f54b97662bd09, f-4aaa3338052773a7f4407489, f-4fd32df5690484eb78f59b4d, f-5f8d3835fe688a0f729a3942, f-61202516994f136e6091ee92, f-6bec43502a8b480f089fefd7, f-6fe1ed233ae9a6a0ad922eb7, f-787dcb8d086f2c38160505b0, f-7a42ac2dfaa770c70a724a4b, f-80052a846a1e672812ba8c69, f-80b5931409ea60efcd866aaf, f-863d364e874ade1ad6f4b374, f-87478608753403c2b2e145b4, f-8f173a658a9ba7cfb649d21c, f-93ee5dccce52316e7d2a78f4, f-9422b19f4f05aff6fc15d13a, f-9458820f0cd7818fec9efa13, f-9839721b2a2c568dbc14d174, f-9df3b4b236ba2a77e0d8bbb9, f-9eba82ef0681f7ae99a8be50, f-9fffccddbded529bce34a313, f-a351571b2d6d4679c6d861c2, f-a45fd2a822522f2fe2d5b83a, f-a5ee68542478b55da3964188, f-abb47df517ef90ae848cb8a1, f-b443f722895e5885dd22790e, f-b9e988a248f3006d4d30e035, f-ba99a0e7f23ec015a97c6cb4, f-c2d9f951c8beeeffcf9c95b9, f-c8fc51421496cc8345c2606b, f-c905094086612ac77453b0bc, f-cb01ecaa5481835dbb6be622, f-cc2ff738cbf6ba39b01b4e32, f-cf6617690e04728082a020c6, f-d05ab1f0ef62bddf626ef83b, f-d0d4fbe854ab9a3f71f2a512, f-d4ab622ae8480ef3d04d4c32, f-d4c78da891ac11ef79ed7c15, f-d99ed10966b675c3b7175ae9, f-da417765af2f7aba5e1fbe3f, f-db0fcbddf13eda0f940301d4, f-df302f9f2b91548d4683d86d, f-e11aeaa3fe71237ef0433155, f-e2155c04e96aa0fb15e854d7, f-e33d0b198080f96adb21d051, f-e7a025c689f28f90cb678400, f-f001b4b83f365a6b47069aec, f-f11cdaaf7e850e7158a7b041, f-f325619be23ad227c3f2fd33, f-f89a3aaf90f806c502958757, f-fab6f2b87448fd7ef6a2d547, f-fd4d2dd05d0922aa216d52bc, f-fdd174a96ca5863a525bf121

ru · official · sha256:4f9496e0a6db3cf907578e0798711c8636c0d41e0fac2b66408aad422fe78ff0RU

§3. Двоичный поиск Задача: по упорядоченной неубывающе последовательности и искомому значению получить позицию какого-либо его вхождения либо признак отсутствия. Вариант — на полуинтервале [lo, hi), с серединой lo + (hi − lo) / 2. Полуинтервал начинается с [0, n). Пока он непуст, берётся его середина; если элемент в середине равен искомому, описание выдаёт эту позицию; если он меньше искомого, левая граница переносится за середину; иначе правой границей становится сама середина. По опустошении полуинтервала выдаётся признак отсутствия. Инвариант границ §1 здесь и есть основание сужения: сравнение с элементом середины вместе с упорядоченностью исключает ровно одну половину, и исключённая половина искомого содержать не может. Мера убывания — длина полуинтервала hi − lo: она строго убывает, потому что середина строго меньше hi при непустом полуинтервале, а перенос левой границы за середину даёт lo не меньше прежней середины плюс единица. Крайние случаи: пустая последовательность — цикл не выполняется, и ответом служит признак отсутствия; повторяющиеся элементы — вариант выдаёт КАКОЕ-ТО вхождение, а не первое, и это существенное ограничение, ради снятия которого написаны §5 и §6. Оценка: не более двоичного логарифма n сравнений, увеличенного на единицу. Нижняя оценка задачи поиска сравнениями совпадает с этой с точностью до постоянного слагаемого — утверждение источника, доказательство остаётся в нём.

Referencing norms: f-03c74abc03c971a1d50aeea6, f-08933dfc39edb81b3b02a6a7, f-0902795e682ef4b0250ad054, f-0b0f74445fedc4f6ba313467, f-0b478f079f765375897da592, f-0c711859e0d3bfc6b481bbfc, f-0db9aada6075876e51a408ad, f-15629fd6558238f1c68bcefe, f-1976f662b103eecfad392946, f-1b0f021d9a60ca2740f342cc, f-1c4a9cf5f228de6beee5a36e, f-1ca4f3cbbbc47d7861a9206f, f-20e359913854b2b7c1913c57, f-2399fef5cfa929e35f6eff3f, f-24935adaab816789b5047df0, f-2e4f11c8a34b38804428794e, f-332bb97bbe568b17566e7bc1, f-33a5ee7f3b30c45847af27a8, f-35ffa7080fc764c68aac8b15, f-36d9d74dacdd5cde2b610a20, f-3b0c04bd615e97b8a5260279, f-3c049075a4bf79d1ab992fa3, f-3c691b197d1bcb2fd30f9702, f-3cf518720a16fb4a6058e34a, f-3e879b22f182929f957aca6e, f-42783b15ad2b48ef58afe04d, f-4a6b930ef10100f1cf49af41, f-4bb06d9d263c4827cb3a4798, f-4ebcef37c28ae7cb90ff2ba2, f-4ef2a791e81f5d74cf99aeca, f-531e9246b65afc9ecf8c7d49, f-53d5a23bec7ca6149b8184e5, f-557fe25af014f81b26541b4b, f-60cf55efd9d2037a3523a174, f-61b4c576ff7763dbde41da66, f-6a803f80054df97395ac6b00, f-6d5171f2de6c1cb8ada3b040, f-6ded7387474310ec3311d9b6, f-6facb99d9f4692de8a6840d2, f-72ecce00ec1b2a1262592e7d, f-73977217388ffb2170fdaf68, f-794d8c7df95da876653f624c, f-798cdf84062639a8d70c394e, f-7a6b99d9a9bc2495c4f70d79, f-7a7471b70e7d9331307b7be7, f-7b6926b0e8960544b02ed185, f-7c0668df479a6f3452ee5d80, f-7cce54e31f572835ef75c040, f-7deccf719afe27e84cca4dd8, f-80ca7c6d43bc0f47a9ad504a, f-8450c17e84dd13c2c005e20d, f-8b3bf1f05e08431e43238586, f-8ce4844afd6f374a2208e06a, f-901b917f752072b4c6b2ab05, f-9162da6bc6e5d7399094207d, f-91ed38e696361f3e8e302762, f-9a860c37c882eba8203e44f8, f-9bc0bf4a8bd983bb10ba0d6e, f-9d124db92c8ff9fd79239726, f-9ecd228626d79363490f948c, f-a5f2de3b2d4f9ebbd83c6550, f-a8530d3303b40b655ff7ad62, f-adbf4be4b55623543a1a0f6d, f-af90a97d83a6aff599ea3d04, f-afa532874d46d2bc28a291f1, f-b0164e0786f82105469f82f1, f-b43b81e2defcde90933bee8e, f-b74e69fe0249f6c6f1aee468, f-b97db512574bb39b1483df6f, f-bce589862a20926cf0e8f61d, f-c06d1bd3f68d63bd0c38005d, f-c48aa099d988c2e6b74e96ee, f-ca94012015431ecfc0e7e559, f-cc330f5d20cc329c925d6f6b, f-cd4670fba6c3db2f1b252a77, f-cd873480414ce9c54b10a363, f-d405d3cbe3c0246bc93fbc28, f-d4a78e6e1509533c4e4bf949, f-d567b2ac80ddedf40c353b46, f-d653ac93dd8bf02a4fe9da9c, f-db2a64d6de41608106490114, f-db88d86bd18c66ecb3c7fcfd, f-dbce514eb0ae4782f472c4a5, f-dcce654e86a7284d5bede48c, f-dff326a4f613ca1809ae2d3f, f-e0afe3579f0290434fd9bdd3, f-e0d1b897f6010d9fe7da863d, f-e375c0b2396cf8b0c96299d0, f-e56cb39ebcf6294393f2252a, f-e5a1e8b84a953424ba6d6394, f-e807dadf810a6daf7efd563c, f-e8cb6a190cc2c99b29661f15, f-ecc660197640e45f2cac0e43, f-ed8e726f9bb6ecf3d24c9289, f-f0acd0c119b8dc760b32a331, f-f12281ba2ef65f1a33195346, f-f1b32e48f0ebef1a514adc30, f-f43c552972c06d8323ff25e4, f-f96c852058da4a5fff9b28a8

ru · official · sha256:608e547aa5b4c3c2e16468113baf4c61d1a2dde1739296ced8f91009c0610551RU

§4. Интерполяционный поиск Задача та же, что у §3, но вариант иной: пробная позиция не середина, а оценка положения искомого по значениям на концах полуинтервала в предположении, что значения растут примерно равномерно. Пробная позиция вычисляется как lo плюс произведение длины полуинтервала на отношение разности «искомое минус значение на левой границе» к разности «значение на правой границе минус значение на левой границе». Далее — как в двоичном поиске: равенство даёт ответ, меньшее значение сдвигает левую границу, большее сдвигает правую. Предусловий у варианта больше, чем у двоичного: последовательность обязана быть числовой и упорядоченной, а деление на разность значений концов требует, чтобы эти значения были различны. Равенство значений на концах есть отдельный случай, и его надо назвать: тогда весь участок состоит из равных элементов, и ответ решается одним сравнением. Оценка: при равномерно распределённых значениях среднее число сравнений имеет порядок логарифма логарифма n; при неблагоприятном распределении вариант вырождается и делает порядка n сравнений, то есть ХУЖЕ двоичного поиска. Оба утверждения принадлежат источнику, и оба обязаны предъявляться вместе: назвать только первое значило бы скрыть цену метода. Пробная позиция обязана удерживаться внутри полуинтервала: при значениях, выходящих за пределы концов, формула даёт позицию вне участка, и описание приводит её к границе. Без этого шага вариант неверен, а не медленен.

Referencing norms: f-01079c774f7b4af9a0eeb111, f-07650b4fdc97e6af00ad3b0f, f-0acf97c03b64d55d6187b404, f-11b3048bcbfa4b79eaa6f286, f-133f589a6be683796c429344, f-142b14a2827e4c15b8725fc2, f-16f6c7f7702304d37eb6815d, f-1b167b3565e82d942613d726, f-1b9ac24932c37c1afd87b556, f-1ce069877080420670f87ad3, f-1f64dc552c251dc35f61de92, f-258176264c3f2b068069d633, f-26846b2ce22059fb6c5c8657, f-26c4d706ed5117aac0a2a8fc, f-2d9177099327758cf504c80c, f-2f453c7bfb4cd1a5978191a3, f-2f9eeb6490b1ff0a2fbc532d, f-329f13797dd885f93f83988f, f-33d8cf936861c8a9ebfa4fdb, f-3b3bb254b07871e4e0bc6c63, f-3c1c6e1c2aeb5fba1960712b, f-3cba8e39f7d277c01f482a0e, f-3d43d466be4b4cae14b447a2, f-3df4f23ba7c1a2625992c178, f-40fafc80c5a7c52aa7f5b1af, f-414d50a2543e3724609538c9, f-446972752ffa1bebdb4f8534, f-44b0f3cf09512646fcde71e5, f-44e2e0ff4585d0a670a9d6bd, f-469e36fb2a5d2fb3dd15e13e, f-4a363a615f5e20320b4c6111, f-4c29891b55dfa1fc8b87c3d6, f-4d7148b2cece406a38e0e791, f-53b4e8eef889cb5219f375c4, f-571057cd4c78aae837fec9ae, f-623d90ca03867da29efc9b1d, f-63b12fce93be55285e00aa23, f-6502f1a09bb93262eb1492ab, f-66499dd1252f6459434f8b7c, f-665aa544eeed5099d528dde9, f-66f382ccd403d6aa89e6007e, f-6c018130b32c6fb12c548de3, f-6cce6e1e888c8e5951f9dd84, f-6e2ba57e1e1df8d9f616a832, f-70dfcf82603ecb59c22679fc, f-7130c866a250e0b860342079, f-73d1f3f0c7362ad11f237fe5, f-791b94cec533b5c6156ed9ca, f-7d6babb3708d56487b2ef50f, f-7e9586fe5fa8adabebd22855, f-7eedfdf3033014db64a9297c, f-7f0fb2daf8b1cd5cf4e7b75a, f-7f45be2f5b21b791544b995a, f-835326164832065f7405c8c8, f-87bd5e336d9e36183b32a8ba, f-883f3a30706f031d9717ca33, f-8be913357da47cf8a227fb9c, f-8bf2ce648c35e8bdae1c6736, f-8c9560ade3f31a39fdd930bc, f-92d050b360e1facd4a53a9b1, f-977e55e061292f79fb4592e7, f-9d779efe2d81e2aa101fcaf7, f-9fea2c601bafab106adb3b2d, f-a0bfab7d632fa652395b93a0, f-a1658d983c0389c43b8545d9, f-a28e7ed4f8f3f4041f66b315, f-a570d9bab889b7fa83ca36f6, f-a9f464d62cfb9bb62789c56b, f-ad353e5b724ad1821e2dabef, f-ae194245aad6e9be45404ab9, f-ae81623eb90dc544f00dbbbc, f-aebbbc72bc3c7831b577e742, f-aec01ee2e84fbc36021a1485, f-af6d157dfe08cf2acc044cd2, f-b5bf1fa485378bd1b31cc3ce, f-b5c385f451032ef00036cc6b, f-b82e73c0a9b0d4797e8655a1, f-b969a0a903d90264f2fe3a70, f-bdd01cfe6d88e12608810702, f-c24062be50c7ab359720e722, f-c2bf4df061fb596c3128acaa, f-c4eff09884ea339b543ac1bb, f-c9b36fbb0afe7ac0a9c52f94, f-ca87f95d1dc842392f3b9bbf, f-caa437d671c2311704abec2e, f-cb4b3a311b6a49ea5e475228, f-cbf76a859d0065e0746ffa0a, f-cdabf2ce2554d54cb84a922e, f-cec4e822611ae19bcea0be38, f-d1acdac8caa82fcddcd1f6aa, f-d1c371817b767bd55f1ed5c6, f-d36e86ba419394de6fa96ddd, f-d578a026316f3ec39fd9cecc, f-d73dddb2813513973bec1cb1, f-d9759d871a9fcf3f52fd0a3e, f-da01af7a32f39f787959e090, f-e0fe1772b5f48201146ba77c, f-e56b8edc719136358c212a70, f-e6703c5665b556b65cfd3f83, f-e6a47dc70b2ee10f75ee2975, f-ebc0a14cadd73749c06e76a7, f-ed458f31ebd709f60a004706, f-ede5765958eed5dea85fdb63, f-f0a3278780a1d1b33e2e0408, f-f0fb881982653a8b5f882426, f-f23980c2d4368f83f11e1601, f-f2c74d9760b9d51aeaa4901e, f-f4025127c3520ffd0cc5824e, f-f7f14e550e6666e653743cb9, f-f8862180b8fbe58b1de4fa16, f-f9282258b6a5268058b94aad, f-fdb441549d575905979d058f

ru · official · sha256:008335ba711827c873ce1c02f9d574ffe8e9137959d77d9e3d30c5b7061e32bcRU

§5. Поиск первой позиции диапазона равных элементов Задача: по упорядоченной неубывающе последовательности и значению получить наименьшую позицию, в которой стоит значение, не меньшее данного. Вариант — двоичный по полуинтервалу, БЕЗ выхода при совпадении. Отличие от §3 состоит в двух вещах, и обе существенны. Первая: сравнение строгое, «элемент меньше искомого», и при истине левая граница переносится за середину, иначе правой границей становится середина. Вторая: цикл не прерывается при равенстве — совпадение не есть ответ, потому что левее могут стоять такие же значения. Инвариант: все позиции левее lo содержат значения, строго меньшие искомого, а все позиции правее hi минус единица — значения, не меньшие искомого. По опустошении полуинтервала lo и есть искомая граница. Результат определён всегда и лежит в пределах от нуля до n включительно: значение n означает, что все элементы строго меньше искомого. Признака отсутствия у этого описания нет вовсе, и это его достоинство: одна величина отвечает и на вопрос о наличии, и на вопрос о месте вставки.

Referencing norms: f-026fb6bb3a0916496f0341bd, f-027b7f32620e3bac7d28deb6, f-034096db229d0487fac52fac, f-03d1bcfe1b366052053a543f, f-05e81788c4424cc18330bfa6, f-06891514bcff70f75755e4f3, f-08867136c536594924ec3f4b, f-0dd6daf4ada96dff43319906, f-0e27d1e6cb65929ec4064ec3, f-1a9f677cad16489dfea33f97, f-1b90d7e02ac3e925fb949287, f-1c558d0632eea54be39c22c8, f-1d4f3007e74303d3f153416c, f-1e47a1feadb17d6aeb0800c5, f-1fc53b70ddbe8a6947bbb4c9, f-23a8208d813eec9f5b500382, f-2c22aaa85cdc100db4c6f0a3, f-3137a3d68b14e5c7035ee66f, f-33a4d48ae24b080ab23418c2, f-3ff24d17f5375dc5c8e8e9af, f-40e4733fd192e16cbef9fbe3, f-46544111cf02c8c3ca750b10, f-4724accf7859bb2202b2df22, f-4772efe7ddaa1067ed0a9ece, f-47fa87989d6a668b3119aeaf, f-484120c03918cbfd2a9c4fe3, f-495095fbf753a1d3762b31ca, f-4956e5274f855acf2b12a3f6, f-4c02c7c77e556387f410b255, f-4fc688866561c09d348fa3c8, f-57cbd60305d518074f0dab8c, f-5c29ce9a583744fe80c191b1, f-5da1a87b6e4249e50b43e38c, f-644c5c5f470d4e3191fa2f00, f-64bf0a8b744e8c7f00a2f532, f-681fc683d3c84af0ab77b870, f-70042011996c4fb5b2f0c8fd, f-741134e995ba2f72f81955fd, f-75616d6186b1cde76ba96d09, f-75a33e6409abf07fa1211b8a, f-75e471f9bbfcc33c22c66c6c, f-7e7a648973a73ccfeb631e3d, f-85660ee08c611fcd29c46733, f-874f0498afac94d121a280fb, f-8d04789179c6df7469b321a3, f-9191370e0c2f3e72d1845ecf, f-91b1ccbbee0561fa3c56ef52, f-9d4119c23010794ccdb0e988, f-a1125a93752f881c29f34688, f-a1dd5c8719696b368ad72c3d, f-a2a42bf9579411ebf814624e, f-a6d6e48663b94b3406355e8b, f-a723ea101981fc1e10f91a52, f-a8556d8206fc034e492f1ad3, f-acae9ad5f6a1903f315774ce, f-ae3724b42d1d94314332277d, f-b04a5d7d43004ea5cb54b6f2, f-b15bc8ad7fc45985aa2622c0, f-b47b10bbac48f1d8d96877ec, f-b5ff21f918b37fc0b1c43c17, f-bbca33467b22799cde869e7c, f-bc81290a6202338cc5c6f957, f-c3e92f04ea77d512513e9d3d, f-c8eb946d297ff3c6097d79a3, f-ceedc1095a98f7c8f16418f5, f-d063003514f6f56cc405988e, f-d0b7e170681304ad54ba97ab, f-d2615fb102bab40c86bbfbe6, f-d6395a8cfa342dfde711c98f, f-d7f320dff7486f0a17ba3e4f, f-dc7ebabeaed4f262c83b9d13, f-e20051b3fe317bdb58e101a0, f-e58327fd0872b20014143dfe, f-e74c5f682e0d5570d1ff66d2, f-e95a8be64ff97c71efc718b8, f-f3246cddd59c594fa2d50e53, f-f4177fdd155f87418f2d63a3, f-f5fed4b79d2b503252fcdd9e, f-f8e5748f79a2b5a516cad21b, f-fa6e32c0c5229af5de965b76, f-ff25056eaf6e3b2f8e87485d, f-ff8bfbc1b03889bc644b357e

ru · official · sha256:11f008fa4eb31378f884c7d38d6165a498c1dc6c4532fea19da458b026ebe06aRU

§6. Поиск позиции за последним элементом диапазона равных Задача: по упорядоченной неубывающе последовательности и значению получить наименьшую позицию, в которой стоит значение, строго большее данного. Вариант — двоичный по полуинтервалу, как в §5, с нестрогим сравнением. Отличие от §5 ровно одно: сравнение «элемент не больше искомого» вместо «элемент меньше искомого». Смена строгости сравнения и есть всё различие между двумя границами диапазона, и оно называется здесь прямо, потому что смешение этих двух сравнений — самая частая ошибка в изложениях двоичного поиска. Число вхождений искомого значения равно разности результатов §6 и §5. Наличие значения равносильно тому, что эта разность положительна; проверять наличие отдельным поиском не требуется. Инвариант: все позиции левее lo содержат значения, не большие искомого, а все позиции правее hi минус единица — значения, строго большие искомого. Оценка у обоих описаний границ та же, что у двоичного поиска: не более двоичного логарифма n сравнений, увеличенного на единицу. В отличие от §3, число сравнений здесь не зависит от того, встретилось ли искомое раньше: цикл проходит полное сужение всегда, и это плата за определённость ответа.

Referencing norms: f-019e44c194cd29dc19040fff, f-030a2f50263d1cbb1b921ab1, f-0719c91431fd4193cf8868fe, f-0949c252ba112fe5d6f2887f, f-0ff215a30a67c9464989bbba, f-127e686a3a8f5369a1678b29, f-1418473809ca47e14f75561d, f-165f4e198a47088abfb23deb, f-18295d2bc13e85aa331fbb1d, f-1845a722e4215a414f23b282, f-1e6dbf65f03dbe4d6e4f4042, f-2c18cdc6d9976f58b7345701, f-2c88269d0f52f450ec6ce4aa, f-2f79998b133f9b59b3cab686, f-39f72d82e5ed58b6d2edae99, f-3a1855897fceba6c26df3d06, f-3a18e2ab4d37580d53e8390d, f-3d7d77cae0db76ca734c770d, f-4070477b2ad4786eb23e5c38, f-40e5d955b7d6779c106c9a1c, f-4121ab41414da841d3e442dc, f-4188c401a4d5c7815dec88c1, f-446ccc12cfbd751a19e4dff4, f-44d66dbf894aa928f3fd16b1, f-48f542e895c0b2b2083c1070, f-4cfaeb07b19d94fd8af49ba2, f-4d26483a76692a21d5779532, f-50658baeb35b3d2bb60a0ee4, f-5c952b083c6cff4b97cf5170, f-5d32363a00cc329aac1cd007, f-5d748fca6bd476ae557f6db3, f-6535a7f2dba373c5eba4f2b8, f-68ab6315d5e0ca0452b269b2, f-6a508ea9aa65c7b44d3c85a3, f-6dec309ec9705ecedd02e2f9, f-6e2636631185fd7a8d78c6be, f-72bf89aaa0905e6d8e14c40d, f-74365d18458283eb41214df9, f-748f889cce21ae4649fa6934, f-77a168bf4b421740a06e1599, f-78850000b0281221f1a2da0f, f-876cf530ba38ea744773917e, f-8856987b461424494aef8b4a, f-8bda572790a39b837a5d01b8, f-8e17c6f72d70ce3fdb9162f1, f-8f0e8b4d3548a14adf15a4bb, f-950078113ef6f262b21f436e, f-9667bd10aa4330dc797a5f45, f-98f6bef579872c12a238d6a6, f-99d7163062fa7f3ef66e539d, f-9c26a9fbc6a18a47e3170883, f-9e97195b658289672644efee, f-a1cc8de835ea565c257f50f6, f-a2f8cc6b69a4462582b73c8c, f-a7e9398a074e930630276241, f-a9b2f6c2e603b62acb5cf9ed, f-adc888aba74cd22a7af4b41e, f-add9d33430d7b642752bef92, f-ae9b84838b7a081cfbec3676, f-af72399a58cc42be74354d1f, f-b0650c6f9f5237b04178eb81, f-bb2f76485f3ac6bcfb382028, f-bd10ae9779e2e8bc6fac23bf, f-c3664dc642ffed9bd4c2e663, f-cc5cecbdc9e7667b55a9f21e, f-cda36477ede88331c98ec07c, f-ceeec96a3721b1a1df8dd805, f-d050238a184106f4165f9234, f-d3a60d3b9e3a82466df9e194, f-d61d2017f350e93b08042f3d, f-d982cc4f4cb64cb0429481d1, f-de5285d858dc32aa3bcf5f93, f-df12f384c18e6649bc8ce38e, f-e18a0c294399e09cd66a031d, f-e4248dd0e9d8bdec241de49d, f-f0386e39d13b91ca15dfaa9d, f-f462dd080cdb0927310ee8d0, f-f562314bda0dbfc8af57f6dc, f-f5c22d44450d7038cdd7d3d2, f-f8af740b79dac355120cc566, f-f906e8bb736df5c624a473dc, f-fb1fa5b44f1fb48c448b68d7

ru · official · sha256:9d31fcef797b9e03f4146a8b488fec5f51d81fdaa4a7b75bb92c7faef9a37455RU

ПОИСК В ПОСЛЕДОВАТЕЛЬНОСТИ: ЛИНЕЙНЫЙ, ДВОИЧНЫЙ, ИНТЕРПОЛЯЦИОННЫЙ И ГРАНИЦЫ ДИАПАЗОНА Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство пяти алгоритмов поиска: линейного, двоичного, интерполяционного и двух поисков границ диапазона равных элементов — первой и последней позиции. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Формулировка шагов, их нумерация и выбор варианта принадлежат настоящему изложению. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни одна последовательность здесь не просматривается.