Найти в отсортированном массиве строку, лексикографически ближайшую слева к данной

@Etyuhibosecyu · Регистрация: 13.07.2017

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

Например, дана строка "банан" и массив "ба, баб, байд, бам, бао, бар, башт", и нужно вернуть "бам". Если строка есть в массиве, вернуть ее саму, причем сделать это за O(logn) и желательно не производить поиск два раза (один раз - на данную строку, второй раз - на ближайшую). Чувствую, что что-то такое есть в C#, будто бы когда-то что-то подобное читал, но конкретно вспомнить не могу. Не поможете?

@QuakerRUS · 26.06.2020, 17:55

Эм. Разве это не обычная сортировка + бинарный поиск? Находим промежуток между большим и меньшим и сравниваем с соседями.

@Etyuhibosecyu · 26.06.2020, 17:57 **[ТС]**

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

Разве это не обычная сортировка + бинарный поиск?

Бинарный поиск, если в массиве нет требуемого элемента, возвращает отрицательное число (если вы о встроенном BinarySearch). А вернуть строку по отрицательному индексу нельзя.

@Toros1992 · 26.06.2020, 18:07

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

Бинарный поиск, если в массиве нет требуемого элемента, возвращает отрицательное число

Вы ошибаетесь. Он возвращает побитовое дополнение индекса первого превышающего элемента

C#
1
2
var arr = new[] { 1, 2, 3, 4, 5, 6, 8, 9 };
var index =  ~(Array.BinarySearch(t, 7)); // 6

Отрицательным числом оно является только для того, чтобы как то отличать его от реального индекса

@Etyuhibosecyu · 26.06.2020, 18:12 **[ТС]**

Toros1992, спасибо! Такой код будет работать?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string[] array = ...;
string target = ...;
int pos = Array.BinarySearch(array, target);
if (pos >= 0)
{
    return target;
}
else if (pos == -1)
{
    return "";
}
else
{
    return array[~pos - 1];
}

@Toros1992 · 26.06.2020, 18:16

Ну да, будет.

Добавлено через 1 минуту
Только напомню, что массив должен быть отсортирован

@QuakerRUS · 26.06.2020, 18:23

C#
1
2
3
4
5
6
7
8
9
10
11
12
using System;
 
class Program
{
    static void Main()
    {
        string[] m = new string[] { "ба", "баб", "байд", "бам", "бао", "бар", "башт" };
        int n = Array.BinarySearch(m, "бан");
        Console.WriteLine(n >= 0 ? m[n] : m[~n - 1]);
        Console.ReadKey();
    }
}

@Etyuhibosecyu · 26.06.2020, 18:31 **[ТС]**

QuakerRUS, ваш код не учитывает случая, когда строка лежит левее всех элементов массива, и, скорее всего, в этом случае вылетит (так как индекс будет равен -1).

@QuakerRUS · 26.06.2020, 18:35

Etyuhibosecyu, добавьте дополнительное условие в проверку, как вы это делали выше. Код был для ознакомления.

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,641 Записей в блоге: 14

	Найти в отсортированном массиве строку, лексикографически ближайшую слева к данной 26.06.2020, 17:50. Показов 2130. Ответов 8 Метки нет (Все метки) Например, дана строка "банан" и массив "ба, баб, байд, бам, бао, бар, башт", и нужно вернуть "бам". Если строка есть в массиве, вернуть ее саму, причем сделать это за O(logn) и желательно не производить поиск два раза (один раз - на данную строку, второй раз - на ближайшую). Чувствую, что что-то такое есть в C#, будто бы когда-то что-то подобное читал, но конкретно вспомнить не могу. Не поможете? 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	26.06.2020, 17:55
	Эм. Разве это не обычная сортировка + бинарный поиск? Находим промежуток между большим и меньшим и сравниваем с соседями. 0

@Toros1992 899 / 554 / 275 Регистрация: 26.11.2015 Сообщений: 1,758 Записей в блоге: 2
	26.06.2020, 18:16
	Ну да, будет. Добавлено через 1 минуту Только напомню, что массив должен быть отсортирован 1

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,641 Записей в блоге: 14
	26.06.2020, 18:31 [ТС]
	QuakerRUS, ваш код не учитывает случая, когда строка лежит левее всех элементов массива, и, скорее всего, в этом случае вылетит (так как индекс будет равен -1). 0

@QuakerRUS 1469 / 1010 / 456 Регистрация: 30.10.2017 Сообщений: 2,799
	26.06.2020, 18:35
	Etyuhibosecyu, добавьте дополнительное условие в проверку, как вы это делали выше. Код был для ознакомления. 0

Найти в отсортированном массиве строку, лексикографически ближайшую слева к данной

Решение