Поиск в сломанном массиве

@Rikkimari · Регистрация: 26.02.2022

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

Формат ввода
Функция принимает массив натуральных чисел и искомое число k. Длина массива не превосходит 10000. Элементы массива и число k не превосходят по значению 10000.

Формат вывода
Функция должна вернуть индекс элемента, равного k, если такой есть в массиве (нумерация с нуля). Если элемент не найден, функция должна вернуть −1.

Изменять массив нельзя.

Мой код

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 def broken_search(elements, target):
    left, right = 0, len(elements) - 1
    while left <= right:
        middle = (left + right) // 2
        if target == elements[middle]:
            return middle
        if elements[middle] <= elements[right]:
            if elements[middle] < target <= elements[right]:
                left = middle + 1
            else:
                right = middle - 1
        else:
            if elements[left] <= target < elements[middle]:
                right = middle - 1
            else:
                left = middle + 1
    return -1

Замечание такое "Обрати внимание, что в строках 5, 7, 8, 13 применяются такие сравнения элементов: == <= <
Если элементы будут пользовательского типа, то придется для них задавать лишние магические методы.
Нужно избавиться от лишних типов сравнений элементов. Достаточно == и <."
Не пойму как мне избавиться от <=?

@iSmokeJC · 06.09.2022, 17:07

if x<y or x==y

@Rikkimari · 06.09.2022, 17:11 **[ТС]**

вот так просто? Я думал более изящный способ есть

@iSmokeJC · 06.09.2022, 17:49

Куда ж изящней?

@u235 · 06.09.2022, 18:09

Что-то не понимаю.. а чем elements.index(k) не устраивает..?

@Catstail · 07.09.2022, 10:24

Rikkimari, а это "сломанный" массив отсортирован? Если нет - я сильно сомневаюсь, что код будет работать.

Python
1
2
3
arr=[15,-8,3,12,0,0,7]    
 
print(broken_search(arr,15))

Вывод -1. А должен быть 0.

@iSmokeJC · 07.09.2022, 10:31

Объясните мне, глупому - почему массив "сломанный"?

Не по теме:

Catstail, я не пойму, это какая-то вариация бинпоиска чтоле?

@Catstail · 07.09.2022, 10:32

iSmokeJC, да, но утяжеленная. И в неупорядоченном массиве не работает. Пример выше.

@Red white socks · 07.09.2022, 12:19

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

Объясните мне, глупому - почему массив "сломанный"?

Посмотрев в хрустальный шар, думаю, что это "одномодальный" массив

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	06.09.2022, 17:07
	if x<y or x==y 0

@Rikkimari 0 / 0 / 0 Регистрация: 26.02.2022 Сообщений: 4
	06.09.2022, 17:11 [ТС]
	вот так просто? Я думал более изящный способ есть 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	06.09.2022, 17:49
	Куда ж изящней? 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,759
	06.09.2022, 18:09
	Что-то не понимаю.. а чем elements.index(k) не устраивает..? 1

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	07.09.2022, 10:31
	Объясните мне, глупому - почему массив "сломанный"? Не по теме: Catstail, я не пойму, это какая-то вариация бинпоиска чтоле? 0

@Catstail Супер-модератор 38173 / 21108 / 4307 Регистрация: 12.02.2012 Сообщений: 34,705 Записей в блоге: 14
	07.09.2022, 10:32
	iSmokeJC, да, но утяжеленная. И в неупорядоченном массиве не работает. Пример выше. 1