Как стать автором
Обновить

Комментарии 345

От сильного стажёра или инженера уровня L3 я ожидаю, что он сможет справиться с двоичным поиском за час

От синьора стоит ожидать что он вообще не будет заморачиваться с двоичным поиском. Потому что в условии задачи про скорость работы ничего не сказано.

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

Первый вопрос, который бы задал я, это - а зачем нам это всё, какую цель мы преследуем и какие сроки имеем? И уже из ответа проистекало бы всё остальное.

НЛО прилетело и опубликовало эту надпись здесь

От хорошего инженера ждут что код соответствует принципам:

reliability

scalability

compliance with requirements

Видно что первые два принципа похожи на NFR (non-functional requirements), но при этом они как бы вне техзадания (3й пункт), в котором может быть куча требований. Потому что любой код по умолчанию обязан быть надежным и скейлиться (учитывать time/../space complexity) если в требованиях явно не указано обратное.

Это всё решается дополнительным "if (n<32)"

В скорости работы и потраченных ресурсах разница будет ничтожна при текущем n (и, скорее всего, линейный поиск окажется и быстрее и менее жручим, чем бинарный при таком малом значении n).

В питоне линейный поиск - 0.070, приведенный автором "примитивный" - 0.053. При тысяче прогонов с x от 1 до 25

А разве пример на питоне?

На самом деле, вопрос правильный, так-как в Питоне фигурные скобки - это set.

Опс, Исправили, пока я писал?

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

переписал на питоне. Постарался один в один. Разумеется список, а не массив.

Список на питоне, это далеко не массив в С/С++/С# и т.п. Для питона почти всегда двоичный поиск будет быстрее.

Переписал на C++. 25 млн вызовов функции (также на входе x от 1 до 25):
линейный - 0.72 - 0.74
бинарный - 1.39 - 1.40
А в оригинале у автора кажется JS. Но на него я переписывать не буду :)

Что и требовалось доказать.

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

У автора код на языке С.

Почему-то для себя решил, что под "автором" понимается Джоэл Спольски - создатель той книги, на которую ссылается цитируемый товарищ. Так вот, Спольски, действительно, сначала практиковал, в основном, язык C, ибо начинал карьеру в Microsoft, значась в команде, работающей над встроенным в Excel скриптовым языком.

А в приведенном фрагменте кода есть служебные слова "function" и "var", которых я не припоминаю в C.

Еще код похож на PHP, но там переменные начинаются со знака $ и, кроме того, длина массива вычисляется как count($arr) (или sizeof($arr)), а вовсе не как $arr.length.

При текущих исходных данных бинарка не только не нужна, но и вредна.

Про размер входного массива ничего не сказано же. Или я что-то пропустил? Ожидается, что вы как раз выясните все ограничения.

Вроде бы 10 элементов размер...

Где? Это тестовый пример на котором задачу объясняли, реальный размер входных данных не написан. Как раз и ожидается, что один из первых ваших вопросов будет про реальные входные данные.

Тогда уж и сортировку никто не гарантирует.

"Массив, фигурирующий в задаче, составлен нарочно таким образом, чтобы не включать 0 и отрицательные числа – это не добавило бы к решению задачи ровным счетом ничего. Элементов в массиве 11, что дает нам пространство индексов от 0 до 10. 10 легко делится на 2, поэтому среднюю точку можно определить без проблем – это число 12"

Т.е. он даже тесткейсы подбирает под исходный набор данных.

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

Не правда. Часто даже навороченный логарифмический алгоритм оказывается быстрее линейного при очень маленьких ограничениях. Например, вот тут уже при n=4 хитрый алгоритм оказывается быстрее. Я мерял.

Тут же самый примитивный бинарный поиск с одним сравнением. Для заданных 11 чисел бин поиск 100% быстрее. Потом, ничего не мешает написать отдельный вариант для коротких массивов и выбирать, какой из двух запускать в рантайме.

Да откуда же сколько ресурсов возьмется на написание всех этих версий, а главное на их поддержку?

Если вам действительно важна производительность во всех случаях, то написать 2-3 разных алгоритма - не проблема. Если же вам достаточно, что ваша программа не станет вдруг падать при внезапном повышении нагрузки, то пишите только бинпоиск и не парьтесь.

Вначале пишут что-бы работало, а потом уже профилируют и рефакторят узкие места. В SAP по крайней мере. Не думаю что в разработке для реального мира выделяют в три раза больше рабочего времени для написания двух-трех разных алгоритмов. Поэтому никто не будет писать двоичный поиск для разового поиска в небольших данных, а если и будут, то только там, где обычный будет ощутимо медленно работать.

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

Если делать не так, то у вас будет тормозить вообще все равномерно.

В идеальном мире? В реальном qsort никто руками не пишет. И оптимальный по производительности это не оптимальный вообще.

И бинпоиск для поиска в массиве никто не пишет, использут какой-нибудь lower_bound из стандартной библиотеки. Но вот когда бинпоиск нужен для поиска по ответу, когда у вас и массива-то никакого нет вообще - его приходится писать руками. Плюс на интервью хочется, все-таки, посмотреть как кандидат решает сложную задачку. Особенно в фаанге-то. Потому что какой-нибудь джон переложить выпускники курсов "мидл с нуля за 2 месяца" еще смогут, а вот что-то посложнее - уже нет. Поэтому приходится заставлять кандидата делать что-то интересное, даже если ему придется делать это редко (а ему придется, в гугле-то, по личному опыту заявляю).

Просто знай, что я уже раз в 20-й натыкаюсь на тебя в разных статьях и везде плюсую. Ты как воин света в одиночку защищаешь саму необходимость думать в программировании. Везде сплошные антиалгоритмисты. Никогда не думал, что доживу до этого момента, когда 99% программистов будут отрицать алгоритмы как явление...

Каждому алгоритму своё мнение. Я вот с пяток сортировок с нуля смогу реализовать, а толку то? За последний год не то что сортировку - поиск в массивах из тысяч элементов не кодил. Это я еще молчу про хеш таблицы на миллионы записей, эти вообще только раз использовал.

когда у вас и массива-то никакого нет вообще - его приходится писать

Нет, именно для этого существует абстракция итераторов и STL. lower_bound / partition_point работает на random access итераторах за O(logN) (и forward итераторах с нюансами, но это тут неважно).

random access range очень легко выдумать например из последовательности чисел

Конечно, можно и стандартные lower_bound натянуть на глобус, но так обычно не делают. Один while написать и короче этих random-access итераторов, и читабельнее сильнее.

В реальном мире"программисты" вроде тебя до сих пор думают, что используется qsort из коробки. Меня даже на собеседовании один тимлид спрашивал про qsort в java collections, на что я ему ответил: там нет qsorta, я не проверял, но я точно могу сказать что это не qsort хотя у обоих сложность O(nlogn). На что он возмутился и утверждал, что qsort. Потом он погуглил и удивлённо обнаружил, что я прав. Откуда я знал? Да хз, просто для меня было очевидно, что при прочих равных надо использовать устойчивую сортировку, и в коробке не может быть qsort так как это неустойчивая сортировка. Но "программисты" не знают зачастую о свойствах устойчивости.

ЗЫ на работу меня тогда естественно не взяли. Задача на собеседовании - ответить достаточно хорошо, но чуть хуже чем интервьюер))

Насколько я помню, там double pivot introspecting sort. Который суть всё тот же qsort, только с оптимизациями.

Да у них в актуальном JDK даже файл реализующий алгоритм называется DualPivotQuicksort.java

Видимо, перепутали. В комментарии речь о коллекциях, а не arrays

Кто и что перепутал?
Тот же List.sort в реализации по умолчанию делегирует всё Arrays.sort.
У ArrayList.sort есть оптимизированная реализация, но вся оптимизация заключается в вызове Arrays.sort без лишних копирований.
Ну а Arrays.sort делегирует всё DualPivotQuicksort.sort

Да уж... Перечитайте ещё раз. Потом можете погуглить, хотя уверен уже многократно пытались. На крайний случай открыть IDE. Шучу, ничего не надо, оставлю просто скриншот о сортировке в Collections. И заметь акцент о стабильности. Можешь попутно погуглить, что это.


Ну и что ваш скриншот вообще доказывает-то? (Кстати, научитесь делать скриншоты меньше, смотреть картинку на весь монитор совсем не интересно)

Я-то, в отличии от вас, в исходники OpenJDK смотрел:

Можете минусовать до талого))) Но если не видите своей ошибки, после того как трижды ткнули, то тут уже ничего не поделать. Даже собственные ссылки, которые беспорядочно нагуглили, не проверили. Ну хотя бы откройте свою же ссылку про Collections.sort или про List.sort и почитайте, наконец, хотя бы java-doc в своих же приведенных ссылках кроме последих двух:

  • This implementation is a stable, adaptive, iterative mergesort

Еще раз: mergesort. От себя добавлю: MERGESORT

Все же дам подсказку: есть такая штука в Java - перегрузки. Ищите свою ошибку.

Там, по идее, не гарантируется, что это именно mergesort - в частности, Arrays::sort(Object[]), который вызывается из List.sort, может использовать либо mergesort, либо timsort. А вот условие устойчивости прописано явно, да.

Там в этих перегрузках чёрт ногу сломит. Да, вы правы, нужная перегрузка и правда использует TimSort, являющийся разновидностью mergesort. Было бы ещё чудесно, если бы вы сразу написали об этом, а не кидали загадочные скриншоты.

Нет, вначале выясняют, какого размера коллекция придет в проде.

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

"Другие" операции делаются и в наивном и в логарифмическом алгоритмах. В логарифмическом их гораздо больше, к тому же.

Еше раз - чем больше других операций, тем больше влияет собственно количество итераций, а не скорость чтения элемента из массива.

Зависит от языка.
На компилируемом 11 значений влезут в кэш процессора и обыщутся быстрее хитрых. Эмпирически есть две границы - 8 и 32 элемента.
Вплоть до 8 сортировать можно хоть пузырьком. А вплоть до 32 искать можно хоть линейно. И только потом начинает вмешиваться О большое.

Я ниже привел результат бенчмарка. С 4 элементов бинпоиск быстрее. Если его вылизать, то, наверное, даже с 3.

Как-раз синьор таки должен сам спросить у интервьюера все параметры задачи, которые явно не прописаны. А которые прописаны - уточнить, правильно ли он их понял. Это тоже показывает уровень. Да, если в результате выяснится, что речь не идёт о гигабайтах данных, то можно и перебором решить. А если задача должна масштабироваться, то алгоритм уже другой. А если супер-масштабироваться, то опять другой. Но всё это идеальный синьор в вакууме должен выяснить и рассказать сам. В том то и суть правильного собеседования.

Уточнить на каком языке должен быть написан алгоритм, на каком устройстве запускаться и т.д. Т.е. времени на само написание кода у него уже и не останется. Зато будет отличное подробнейшее ТЗ для джунов.

Как будто что-то плохое... )) В идеале задача и должна быть так поставлена, чтобы по ТЗ её уже любой джун мог запрограммировать )) Суть синьора во многом именно в том, чтобы хорошо декомпозировать и описать задачу. А что касается языка, то на таких собесах бывает вообще пишут код на псевдокоде в нотепаде. Потому что по конкретному языку и его теории - это отдельное собеседование, а тут про алгоритмы.

Да, правильный синьер должен интервьюера загнать в тупик, ну или схантить на худой конец.

От сеньора стоит ожидать как минимум замечание, что типы параметров не определены и а.length вполне может выкинуть исключение, так же как и а[i], и любая операция сравнения (больше, равно, меньше), если эти операции не определены для данного переданного типа.

Автору: не хватает как минимум еще двух тестов - с передачей неправильных типов для первого и второго параметров.

Неправильно;)
Синьор должен перед решением уточнить, что от него хотят, или, для чего и где это будет использоваться.

Если предположить, что поиск нужен по этому конкретному предложенному массиву (а это можно предположить из объяснения решения от автора, но я бы уточнил у интервьювера), то не надо тут ни логарифмов, ни O(N). Задача решается за O(1): готовим массив из 21 элементов с ответами. Выходы за границы (0 и 21) обрабатываем отдельно.

Кроме того, массив для бинарного поиск должен быть упорядочен, а потому, надо его предварительно сортировать. В общем бинарный поиск чисто для теоретиков. Действительно ни один вменяемый сеньор этой фигнёй заниматься не станет.

Я вам в другой ветке уже ответил. Повторю тут, чтобы у читающих не возникало ложного мнения вашей правоты.

Применяется весьма часто.

Ваш ответ не имеет ничего общего с реальностью к сожалению.Потому я даже не стал ваш ответ комментировать.
Тут 2/3 комментаторов знают что бинарный поиск чисто теоретическая задача, оторванная от реальности, а вы своё всё пытаетесь всем внушить.

Нет, вы не правы совершенно, бинарный поиск действительно не применяется на практике, что отметил не только я. Можете хоть 1000 минусов мне поставить - это ваш уровень.

Что значит "не имеет ничего общего с реальностью". Я вам привел КОД с реального, большого, популярного проекта, где бинарный поиск используется. Это вы связь с реальностью потеряли.

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

Потому да, решали бинарным поиском, и чисто для "галочки". С тех пор (а это почти 30 лет в IT) мне этот бинарный поиск ни разу нигде не пригодился, от слова совсем. Нет никаких прикладных задач, где он бы мог помочь.

Нет, специально под него сортирнуть массив, можно конечно, но зачем?
Есть другие, более быстрые способы поиска, и прежде всего индексирование (в т.ч. использование хэшей и словарей.)

Наверное, я туповат, но формулировка "ближайшее наименьшее число" не очень ясна. Может, стоило написать "ближайшее число, которое меньше или равно заданному"? По крайней мере, судя по тест-кейсам, предполагается именно это. Эх, не быть мне L5, "некоторые просто не понимают, чего я от них добиваюсь" )

формулировка "ближайшее наименьшее число" не очень ясна.

Она вообще какая-то противоречивая. Т.к. оба определения - и "ближайшее", и "наименьшее",- по тексту совершенно равноправны. Хотя по смыслу нужно наименьшее из ближайших. При обратном приоритете вообще ничего не получится - наименьшее в это массиве всегда первое, вне зависимости от чего-либо (при условии, что массив соответствует условию).

Я бы, наверное, сказал "наибольшее число, не превышающее заданное".

Т.к. оба определения - и "ближайшее", и "наименьшее",- по тексту совершенно равноправны. Хотя по смыслу нужно наименьшее из ближайших

Так вроде приоритет правильно указан - сперва ближайшее, потом среди ближайших наименьшее, если есть равноправно удаленные ближайшие.

Так вроде приоритет правильно указан - сперва ближайшее, потом среди ближайших наименьшее, если есть равноправно удаленные ближайшие.

По правилам русского языка - всё с точностью до наоборот. Если считать определения неоднородными, то первое относится к комбинации второго определения и существительного. И получается "ближайшее из наименьших". А поскольку в сортированном [по возрастанию] массиве "наименьшее число" - это без вариантов первое число массива, то дополнительное "ближайшее" вообще лишено смысла, ибо ему приходится выбирать гарантированно из одного варианта. Ну или из ничего, если массив пуст.

Эта нелогичность и заставляет считать определения однородными.

В случае же неоднородных определений должно быть написано наоборот - "наименьшее ближайшее число". Тогда всё ровно - ближайших либо одно, либо два, и из них наименьшее.

Впрочем, по смыслу эти определения и правда неоднородны, ибо рассматривают разные свойства числа - "ближайшее" рассматривает местоположение, а "наименьшее" - значение.

а ведь можно просто сказать "ближайшее меньшее число", и все неоднозначности уйдут

Да и метрику расстояния не задали. Вообще не понятно, что он от людей хотел)

ну вот для числа 13, ближайшее наименьшее будет 12, а не 14.
А для числа 8, ближайшее наименьшее будет 9 (а не 6)

Я по-прежнему не понимаю, почему для 2 ближайшее наименьшее найдено не будет, а для 22 - пожалуйста. В остальном вы правы, моя переформулировка не является верной.

Нужно найти число, которое
а) меньше или равно входному
И
б) содержится в массиве

Если входное число (22) превышает максимальный элемент (21), то очевидно, что максимальный элемент и будет ответом.
Если входное число (2) меньше минимального элемента (3), то очевидно, что массив не содержит искомого числа, значит ответ == -1

Нужно найти число, которое

а) меньше или равно входному

Это откуда такое? Читаем задание:

которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.

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

f(a, 2) = -1        // Число слишком мало и выходит за границы массива

лично мне кажется не соответствующим исходному заданию. Для переданного числа 2 ближайшее, и оно же наименьшее, одно - это число 3, первый элемент массива. И ошибки - как-то не видно. Так что откуда -1 в ответе - ну совсем непонятно.

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

Ткните мне пальцем в требование, чтобы результат не превышал заданное число... я лично такого требования не нахожу.

Я так понял русскоязычную формулировку, а дальнейший текст это подтвердил. Оригинальная (англоязычная) формулировка мне нравится меньше, но примеры всё же позволяют [мне] догадаться. Хотя, да, я бы всё равно уточнил.

Возможно, формулировка специально дана в таком виде, чтобы посмотреть на реакцию кандидата.

Не прошли собеседование =)

Ближайшее, а не "меньшее или равное".
Из ближайших - меньшее, если ближайших несколько на равном удалении.

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

Тогда примеры не соответствуют ТЗ.

Только один, но это вопрос к автору

В оригинале

Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.

И в моём восприятии это даже хуже, чем "ближайшее наименьшее число"

Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.

я бы написал return x, x - 1 , в задании ведь нигде не сказано, что число должно браться из a. Потом бы мне не дали оффер, и я написал бы статью о интервьерах, которым не нравится, что их ловят на неточных заданиях )))

А почему вы взяли целое? Нигде ведь не указано....

Потому что для вещественных (можно и комплексные докинуть, не жалко) чисел не существует next. Так что берём такие, для которых это понятие имеет смысл.

Для вещественных не существует. Для float/double вполне себе существует.

Потому что нормальная формулировка - next smaller element. А тут просто вообще от балды написано.

а почему next а не previous???

наверное потому, что next smallest означает previous (или должно означать по мнению автора текста; я не настолько хорошо знаю английский)

Так слишком понятно. Кандидат не запутается. Но судя по тестам OP хотел: the closest equal or smaller number.

просто ваш английский видимо слишком запутан ассоциацией что next это всегда следующий. А в оригинале это просто соседний, неважно в какую сторону. Girl next door, это не обязательно она живет справа.

ИМХО, это кривая формулировка. Next (в смысле closest) подразумевает что искомый элемент в массиве есть, у него есть конкретная позиция, и надо взять ближайший к этой позиции. А учитывая что это не так (элемента в массиве нет), то получается какая-то ерунда.

Как по мне, в задании указано: "Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки. " - функция должна возвращать два числа: "Х" и "ближайшее наименьшее число" или "-1" в случае ошибки. Явно же не указано, что возврат подразумевает одно из чисел.
То есть f(a, 12) = 12, 10

Явно же не указано, что возврат подразумевает одно из чисел.

Так там же перечисление с "или". Откуда вы взяли "и"?

Define a function f(a, x) that returns x, the next smallest number, or -1 for errors.

x, наименьшее соседнее число или -1.

x, наименьшее соседнее число или -1.

Тогда функция, если X is not None, возвращающая X, иначе если существет следующее наименьшее соседнее число, то его, иначе -1, это решение?

Ну, кривая же формулировка. Только по test-caze'ам и восстанавливать правильную.

Так там ещё

У нас есть массив, отсортированный по возрастанию
a = […]
напишите f(a, x)

Поэтому мы пошлём null

f(null, x) = -1 // Неверные аргументы

А можно туда и колбэк послать? Не говоря ещё и про сортировку

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

Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.

Изи

f(a,x) = x

В следующий раз не ленитесь.

Find X

Разворачивая вашу мысль для тех, кто не понял:

В задании вообще ничего не сказано о том, что возвращаемый результат функции должен быть элементом массива. Кое-как об этом можно догадаться по тестовым примерам, но, мягко говоря, с трудом.

И, например, совершенно не очевидно что f(a,2)=-1 - на первый взгляд f(a,2)=2 вполне валидно. Из условия задачи вообще не следует, что х за пределами массива является ошибкой.

Абсолютно верно, а вообще нельзя получить верное решения задавая не верный вопрос.

PS: я бы сказал задающему такую задачу что что к Вас ошибка в примерах и пускай сам думает в чем трабла.

К сожалению, в реальности вы в неравных условиях. Задающий задачу уже работает в Гугл, получает огромную зарплату и имеет ещё более огромное ЧСВ, не умея корректно формулировать элементарную задачу. А получение вами работы зависит от абсолютно субъективного мнения этого самого задающего о вас.

Тут как посмотреть, не только компания выбирает работника, но и работник выбирает где ему работать.

Ну и в больших компаниях заведено правило фидбека на интервьюера даже если ты не прошёл.

не умея корректно формулировать элементарную задачу

Почему вы решили, что не умеет, а не делает это специально? В обычной ситуации задачи тоже часто недоформулированы и содержат двусмысленные формулировки. И как раз смотрят, в том числе, на то, как человек себя поведет - добъётся ясности или побежит программировать как понял, выдав не то, что нужно, в итоге. Если программист на интервью получил задачу, ничего не спросил и пошёл писать код, это жирнейший минус и, скорее всего, проваленное интервью.

В статье именно так и произошло. Автор криво-косо что-то написал, назвав это задачей. Потом ничего не уточнил и побежал писать код. Получается, что автор статьи провалил интервью и как интервьюер, и как соискатель?

Даже странно, что в такой длинной статье не указано это самое быстрое и соответствующее ТЗ решение. Может это ловушка и на самом деле он нанимает только тех, кто так отвечает?

f(a, 2) = -1        // Число слишком мало и выходит за границы массива

f(a, 22) = 21       // Число слишком велико и выходит за границы массива

f(a, 3) = 3         // Левая граница массива

f(a, 21) = 21       // Правая граница массива

А при чём тут вообще границы массива? Предметная область не определена. Формулировка задания ни полслова о границах не говорит. Получается, что либо задание не соответствует задаче (иначе откуда такая забота о границах?), либо финально от кандидата требуют не "реши задачу". а "угадай, что я задумал".

f([], x) = -1       // Массив пуст

Ну вообще-то у нас есть начальное условие "У нас есть массив, отсортированный по возрастанию". Кто бы мне рассказал, как может быть сортирован пустой массив.

Как правило, после небольших подсказок, кандидат приходит к следующему списку

Интересно, почему кейс с несоответствием первого аргумента рассмотрен, а второго - нет..

с пустым массивом ещё ладно, он проходит проверку на source == source.sorted()
но вот когда просят тест-кейс на невалидные типы данных, типа nullable при лайвкодинге на языках с null-safety - это вообще странно. но такое наблюдаю часто.

Это от шизы и не знания SOLID конкретно буквы S. Часто вижу что люди не могут осознавать что эти принципы можно применить даже к методу. В случае написания алгоритма я предполагаю что обязанности проверок данных лежит на коде выше.

Защитное программирование говорит, что все входные параметры надо обязательно проверить, если только это не сказывается на быстродействии; так что незнание буквы S тут ни при чём.

Проверка на null в языке с null-safety - это либо просто шиза, либо привычка работать с устаревшим кодом, либо привычка работать с коллегами, которые проверки null-safety обходят.

защитное программирование разве не предписывает проводить проверки на стыке систем и библиотек, а не в каждой функции?

а ещё есть принцип garbage in - garbage out - когда странно ожидать от кода адекватного поведения, если вызывающая сторона сама передаёт фигню вместо данных.

В общем, считаю, что тут вопрос религии, каким делать контракт, и конфессию на собесе можно уточнить, но за неуточнение я бы точно не списывал балл разрабу в данной конкретной задаче.

Пустой массив вполне себе отсортирован, на нем установлено отношение порядка.

Для него работает правило "каждый последующий элемент не меньше предыдущего".

каждый последующий элемент не меньше предыдущего

В такой формулировке получается, что в пустом массиве существует некий "предыдущий". Поэтому лучше так: "каждый элемента массива не меньше всех предыдущих"

Не получается.

Квантор всеобщности на пустом множестве даёт истину.

Ну вы серьезно!? Да, я некорректно выразился, думал, что это очевидно и поэтому написал небрежно. Я имел ввиду если в массиве множество предыдущих элементов пусто. При этом сам то массив может быть и не пустым, а состоять из одного элемента, например.

Как вы будете применять квантор всеобщности в этом случае?

Зато вас заплюсовали, местная аудитория поражает своей глубиной мышления, и умением проверять массивы на граничные случаи)))

Так же. Формулировка "каждый последующий [...] предыдущего [...]" означает применение квантора всеобщности к множеству последовательных пар индексов.

У массива из одного элемента это множество такое же пустое как и у пустого массива.

Вы берете массив из одного элемента, применяет к нему рекуррентно правило "каждый последующий элемент не меньше предыдущего" уже на первом же шаге у вас существует последующий элемент - это единственный элемент массива*, а значит, чтобы массив был отсортирован должен существовать предыдущий, а его не существует.

(*) В противном случае надо отдельно определить, является ли первый элемент массива последующим или нет, и вообще по-хорошему надо определить, что такое последующий элемент. Вот вы наверное считаете, что первый элемент не может быть последующим, но это не очевидно и зависит от договоренностей.

P.S. экой вы, батенька, токсик. Минусовать в математическом споре о трактовках понятий - это сильно.

Формулировка "каждый последующий [...] предыдущего [...]" означает применение квантора всеобщности к множеству последовательных пар индексов

Ну только если только в такой трактовке про "последовательные пары индексов". Ну это уже какое то домысливание... Тогда лучше так и прописать условие, что "для всех последовательных пар индексов выполняется..." И ещё определить что такое последовательная пара. В общем либо неоднозначность, либо сильное переусложнение формулировки. Поэтому лучше пользоваться формулировкой "каждый элемент не меньше всех предыдущих " тут нет никаких неоднозначностей и домысливаний.

Но ведь в нём каждый элемент имеет неопределёное значение. А для неопределённых значений неопределена операция "<".

Нельзя так свободно пользоваться отрицанием под квантором всеобщности. Отрицание превращает его в квантор существования.

Иными словами, если вы желаете указать, что к неопределённым элементам неприменима операция "<".- вам надо предъявить такой элемент, недостаточно сказать что они там все такие.

Ну я чисто с практической точки зрения.

irb(main):005> a = []
irb(main):006> a[0] < a[1]
(irb):6:in `<main>': undefined method `<' for nil:NilClass (NoMethodError)

У вас в массиве нет 0 и 1 элементов, с чего вы вообще пытаетесь их сравнить? Условие "каждый последующий элемент не меньше предыдущего" ничего не требует относительно элементов с индексами 0 и 1 на пустом массиве.

Число практически пройдитесь по пустому массиву циклом и проверьте это условие в цикле.

У вас в массиве нет 0 и 1 элементов, с чего вы вообще пытаетесь их сравнить?

Так и я о том же. "каждый последующий элемент не меньше предыдущего". Как это понимать в случае с пустым массивом?

Условие "каждый последующий элемент не меньше предыдущего" ничего не требует относительно элементов с индексами 0 и 1 на пустом массиве.

КМК, это требует как минимум, их наличия. Если их нет, то какие могут быть дальнейшие рассуждения о них?

Иначе ведь к такому массиву одновременно применимо и условие "каждый последующий элемент не больше предыдущего".

Число практически пройдитесь по пустому массиву циклом и проверьте это условие в цикле.

Чисто практически это невозможно.

a.each_index { |i| puts a[i] < a[i+1] }
=> []

Иначе ведь к такому массиву одновременно применимо и условие "каждый последующий элемент не больше предыдущего".

Совершенно верно. Поэтому пустой массив (как и массив из одного элемента) является отсортированным независимо от критерия сортировки - по возрастанию ли, по убыванию или с произвольным нетривиальным компаратором, неважно.

Чисто практически это невозможно.

Ну как же "невозможно", если вы ровно это и сделали в коде ниже? (Другой вопрос, что этот код не совсем верен, потому как на реальном отсортированном массиве в конце будет проверка something < nil, которая выбросит ошибку)

Ну как же "невозможно", если вы ровно это и сделали в коде ниже?

Разве? Я только попытался. Блок не выполнялся даже, значит проход по массиву не осуществлён.

Другой вопрос, что этот код не совсем верен, потому как на реальном отсортированном массиве в конце будет проверка something < nil, которая выбросит ошибку

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

Блок не выполнялся даже, значит проход по массиву не осуществлён.

Ну как это не осуществлён? Цикл же завершился. А то, что в нём не было ни одной итерации - это уже несущественно.

Вы с ним по разному смотрите на формулировку "каждый элемент ...". Он считает, что должен существовать хотя бы один элемент массива, к которому правило было бы успешно применено, а вы - нет.

Лично мне импонирует его вариант, а не ваш, ибо в случае с вашим любой пустой массив подходит под любую арбитрарную формулировку, например "каждый элемент массива должен присылать мне по 100 биткоинов". И пустой массив, по вашему мнению, это вполне реализует, что выглядит довольно абсурдно.

И тем не менее, математически это именно так - любое утверждение с квантором всеобщности (т.е. "каждый элемент имеет свойство X") тривиально верно для пустого множества, а значит, и для пустого массива.

Да, но чтобы в подтверждение своих слов можно было приводить некую математическую теорию, нужно сперва обоюдно договориться, что в контексте дискуссии это дозволено делать. Я бы, например, на такое определение не согласился, т.е. у меня свои собственные взгляды на логику.

И не только у меня, например, в шарповом фреймворке linq функция All() (да и Any() тоже) пошлет эту вашу математику нафиг, если в перечислении не будет ни одного элемента.

А разговор то наш алгоритмический гораздо ближе к программированию, нежели к математике.

И не только у меня, например, в шарповом фреймворке linq функция All() (да и Any() тоже) пошлет эту вашу математику нафиг, если в перечислении не будет ни одного элемента.

Да ну?

var seq = new int[0];
Console.WriteLine($"All: {seq.All(x => x > 0)}"); // true
Console.WriteLine($"Any: {seq.Any(x => x > 0)}"); // false

Всё в полном соответствии с правилами исчисления предикатов.

Ужас какой, надо ж было так косякнуть. Штош, правда ваша.

А при чём тут вообще границы массива?

Просто типовая ошибка у начинающего будет на пограничных случаях. Когда, скажем, все элементы больше или все элементы меньше. На то собственно тесты и нужны, чтобы покрывать всякие хитрые кейсы.

от кандидата требуют не "реши задачу". а "угадай, что я задумал".

Собственно на любом собеседовании так. Нарочито дают размытое объяснение, чтобы выяснить насколько кандидат в состоянии прояснить ситуацию задавая правильные вопросы. Очень полезный навык в разработке.

как может быть сортирован пустой массив.

А что не так? Пустой массив всегда отсортирован.

Интересно, почему кейс с несоответствием первого аргумента рассмотрен, а второго - нет..

Кажется интервьювер немного дурачок странный

Я когда начинал читать - то ожидал не два уровня, а побольше. Что на первом решают в лоб за один проход. На втором - двоичным поиском, а на третьем какая-нибудь магия вроде кода Грея или еще какой-то малоизвестной штуки. Увы, ожидания не оправдались.

Определите функцию f(a, x), которая возвращала бы x, ближайшее наименьшее число или -1 в случае ошибки.

По формулировке вообще непонятно, что нужно сделать.

Автор еще и сам же удивляется:

Еще кое-кто не понимает, чего я от них добиваюсь таким вопросом. 

Действительно, почему бы это :)

Я не совсем знаю, как именно у вас проходит собеседование, но по хорошему стоит предпреждать кандидатов об алгоритмической секции, т.к. много людей могут реализовать бинарный поиск, но по памяти это могут сделать довольно мало людей, т.к. по сути это бесполезное для работы знание. С тем же успехом можно просить людей реализовать быстрое преобразование Фурье или поиск в глубину/ширину. Да это покажет что собеседник разбирается в алгоритмах. Я согласен, что человек должен был бы сказать что тут нужно применить бинарный поиск и написать возможные тест кейсы, но на мой взгляд полезнее увидеть что человек понимает алгоритм и если что сможет его реализовать, а не просто выписать заученное решение с литкода, но если вы разрешаете гуглить во время собесов то это скорее норм, т.к. большую часть кода человек будет брать из готовых источников, либо хотя бы из готовых формул или схем

Я сам узнал об этом вопросе от коллеги из Google. 

Я бы не хотел обижать, но для faang такие вопросы норма, т.к. они очень хорошо платят + есть шанс вырасти до зп 500к$+ и у них еще явно прописаны рекомендации для подготовки кандидатов. У нас во многих компаниях (не во всех), тоже тащат алгоритмическую практику, но кандидат узнает на собесе и само собой многие отсеиваются, т.к. ты пришел поговорить о работе, а тебя просят красно-черное и свою очередь, а ты последний раз сталкивался с таким на паре 10 лет назад и тебя не предупреждали что это будет нужно на собесе, ну как бы не совсем нормальное отношение к кандидату. В целом как бы собеседующий определяет вопросы, но по факту вы так можете потерять реально много подходящих кандидатов, но если вакансия просто для поиска хороших кадров, а работа не горит, то наверное такое "допустимо" делать

НЛО прилетело и опубликовало эту надпись здесь

Надо вводить Литкод в ежедневную привычку, как зарядку. Проснулся - завтрак, урок в Дуолинго и задача в Литкод, а потом уже за работу)

реализовать надо максимально сложно и за один час! Предварительно самостоятельно догадавшись, что же реально хотел получить автор.
Внимание вопрос. Чего же реально хотел получить автор? Работника? Или мнение о себе, как о лице, даже не способного адекватно поставить задачу, и назначить на её решение адекватный срок реализации (точно уж не час).

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

Это же собеседование в гугл. Там еще рекрутер выдает ссылку на книжки и курсы:

За время работы в Google я провёл более двух сотен интервью.

Довольно интересно, что вы рассматриваете в тест кейсах null в качестве некорректных данных, но не рассматриваете очевидный кейс - неотсортированный массив. А если массив проверять, то вся магия бинарного поиска сразу ломается, ибо проверка исходных данных все равно займет O(n). Поэтому применение бинарного поиска одновременно с проверкой всех граничных условий не имеет смысла - вы либо уверены в своих данных, либо нет.

Интересно послушать умников, на счет указания уже отсортированного массива в условиях задачи.
Как по мне - доверять такому можно, только если ты сам предварительно отсортировал его (как вариант получил из базы с order by).
Если данных мало - я бы еще раз его отсортировал для гарантии, а если много...
тем более: лопатить цифры неделю, чтобы потом оказалось, что входные данные были не нормализированы.

если ты сам предварительно отсортировал

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

Сортировка отсортированного массива в лучшем случае займет O(n). За это же время работает перебор неотсортированного массива.

В случае этой задачи выходит что либо давайте нам на вход любой массив, либо поклянитесь мамой )

Но в общем случае сортировка массива может быть одной из самых лёгких операций в функции

Ну, не обязательно. Бывают ситуации когда в одних данных мы уверены, а вот в других нет.

Как пример - массив мы получили из подконтрольной нам БД, отсортированный по индексу, и мы довольно уверенны в том что там нормальная сортировка. А другие параметры получили из реста, и тут нам прилететь может все что угодно.

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

я бы начал искать с середины массива:

def find(a, x):
    if not isinstance(a, list) or not len(a):
        return -1

    pos = len(a) // 2
    step = 1
    res = -1

    if a[pos] > x:
        step = -1
    else:
        res = a[pos]

    while True:
        pos += step

        if pos == -1 or pos == len(a):
            break

        if a[pos] <= res:
            return res

        if a[pos] <= x and a[pos] > res:
            res = a[pos]

    return res

или на js:

function find(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let pos = a.length >> 1;
    let step = 1;
    let res = -1;

    if (a[pos] > x) {
        step = -1;
    } else {
        res = a[pos];
    }

    while (true) {
        pos += step;

        if (pos === -1 || pos === a.length) {
            break;
        }

        if (a[pos] <= res) {
            return res;
        }

        if (a[pos] <= x && a[pos] > res) {
            res = a[pos];
        }
    }

    return res;
}



А ваше решение имеет проблемы:

// про плюсы отбития блоков пустыми строками вы похоже не слышали
function f(f, a) {
  // а что если здесь не массив а объект?
  // кроме того условие и код в одну строчку это плохой стиль 
  if (a == null || a.length == 0) return -1;

  // Общепринятая семантика это result, а не answer
  // и почему var, а не let?
  var answer = -1;
  var low = 0;
  var high = a.length — 1;
  while(low <= high) {
    // Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1
    // и как то сложно, я таки не понимаю зачем это делать в цикле.
    var mid = Math.floor((low + high) / 2);
    if (a[mid] == x) {
      return x;
    }
    // нафига тут else если перед ним return?
    else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid — 1;
    }
  }
  return answer;
}

В итоге я бы вас не взял с таким решением

Вы это серьёзно? Предлагаете заменить логарифмический алгоритм на линейный из-за проблем с … оформлением?! Да ещё и разновидности "вкусовщина"?

про плюсы отбития блоков пустыми строками вы похоже не слышали

От чего отбивать-то его предлагаете? Это ж начало блока кода...

кроме того условие и код в одну строчку это плохой стиль

Пока код короткий - сойдёт.

Если перенести тело на следующую строчку - то окажется, что не писать фигурные скобки - плохой стиль, а если написать ещё и фигурные скобки - это будет три строки на, в общем-то, избыточную проверку.

и почему var, а не let?

let при определённом положении звёзд может оказаться медленнее, в этом году даже пришлось стандарт править чтобы у браузеров появился шанс это замедление убрать.

Не то чтобы это замедление было и правда важно, но и считать использование var чем-то плохим в критичном к производительности коде не стоит.

Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1

Вот тут вы правы, Math.floor - тяжёлая операция, не фиг её делать лишний раз.

и как то сложно, я таки не понимаю зачем это делать в цикле.

А вот этого высказывания уже я не понимаю. low и high меняются между итерациями цикла, где ещё можно вычислить mid?

нафига тут else если перед ним return?

Чтобы подчеркнуть альтернативность трёх веток кода.

  1. я нигде не предлагал заменить предложенный алгоритм на мой. Просто написал простой алгоритм который первый пришел в голову, а потом рассмотрел предложенное решение. Не надо выдумывать.

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

  3. дополнительный нестинг усложняет читабельность, это всем известный факт который указан в книках по рефакторингу.

Вы так и не ответили, откуда именно вы собрались отбивать функцию f.

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

Это всего лишь вкусы авторов книг по рефакторингу.

я имел в виду отбитие блоков внутри функции.
хорошая практика что любой блок который занимает более одной строки отбивается пустыми строками. Хорошая практика никогда не писать if (foo) return 1, читается проще.

Как-то так:

function f(x, a) {
if (!Array.isArray(a) || a.length === 0) {
return -1;
}

let result = -1;
let low = 0;
let high = a.length — 1;
let mid;

while (low <= high) {
mid = (low + high) >> 1;

if (a[mid] == x) {
return x;
}

if (a[mid] < x) {
result = a[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}

return result;
}


Обратите внимание, что я также вынес объявление mid за пределы цикла.

P.S. Ну да, авторы руководств по рефакторингу дураки, а вы нет.

Отбивать цикл от переменных цикла - глупо, это один логический блок.

Из трёх альтернативных веток кода отбивать одну от двух других - тоже глупо. Вы же блок if от else не отбили? Тогда почему ветка ==x оказалось отбита от ветки <x?

С необходимостью отбить return result; я бы тоже поспорил, это логическое завершение цикла.

Осталось два места где можно поставить пустые строки - после входной проверки размера массива, и после вычисления mid. Но вторую я бы тоже не ставил, поскольку она разорвёт пополам единый цикл, и вообще вычисление mid можно считать частью последующего сравнения.

PS иронично, что в попытке указать другим на недостатки в оформлении кода, вы упустили из своего кода все отступы.

так. еще раз по пунктам.
в приведенном решении есть несколько проблем:
1) код плохо читается
2) нет проверки на то что входное значение может быть не только null но и чем угодно, например объектом или строкой
3) использован тяжелый метод Math.floor
4) одна из переменных объявлена внутри цикла, что лишние
5) код не универсален, следовало бы оформить его чтобы мможно было переиспользовать с любым компаратором.

Поэтому конечно я бы не стал брать автора. То что я бы его не взял исключительно из-за нечитаемости кода, это ваши выдумки

p.s. и да, вы придрались к парсеру хабра, а не ко мне.

 код плохо читается

Код читается достаточно хорошо для понимания. Можно и лучше, но приведённого автором оформления достаточно.

Для сравнения, ваш код из комментария чуть выше читается ужасно. И нефиг гнать на парсер Хабра, его синтаксис и раньше был не сильно сложным в освоении, а уж в WYSIWYG-то редакторе лепить подобные отмазки должно быть стыдно.

одна из переменных объявлена внутри цикла, что лишние

Почему? В какой книге по рефакторингу вы вычитали, что объявлять переменные внутри цикла - плохо?

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

Этот пункт вы вообще только сейчас упомянули.

  1. В редакторе код выглядел нормально и там были отступы. Даже при последующем редактировании. Кроме того вы спросили где бы я добавил пустые строки, я вам показал. Так что ваши придирки к отсутствию индентации не имеют никакого отношения к обсуждаемому предмету.

  2. Потому что нефиг рассчитывать на оптимизатор, я хз будет ли он выделять память для переменной каждый раз или сможет оптимизировать и вынести выделение памяти за пределы цикла. Это база, мой друг.

  3. Я не пишу на js и с утра не было времени чекнуть есть ли там готовый метод findLast в js и если нет писать его реализацию. А он есть и соответственно весь этот код превращается в велосипед.

Потому что нефиг рассчитывать на оптимизатор, я хз будет ли он выделять память для переменной каждый раз или сможет оптимизировать и вынести выделение памяти за пределы цикла. Это база, мой друг.

А вот если бы использовали var - такого вопроса бы не стояло.

А вообще, звучит не как "база", а как глупость.

Ну зачем мы меня заставляете объяснять базовые вещи?

Использование var потенциально может привести к багам, если кто-то будет дорабатывать эту функции и заюзает переменную mid выше цикла и не обратит внимание на то что она используется где-то там в ниже в цикле и будет соответсвенно ожидать то значение которое было туда записано до цикла.

references:
https://hackernoon.com/why-you-shouldnt-use-var-anymore-f109a58b9b70

https://dev.to/mindninjax/stop-using-var-for-declaring-variables-2p3a

Вы так пишете, как будто с вынесенным из цикла let не будет точно такой же проблемы.

И да, иронично что по первой из ваших ссылок во всех примерах кода весь код записан в одну строку. Видимо, тоже парсер Хабра виноват.

ну вот вам пример

function foo() {
    var x = 1;
    const arr = [1, 2, 3, 4, 5];

    for (let i = 0; i < 5; i++) {
       var x = arr[i];
    }

    console.log(x);
}

function bar() {
    let x = 1;
    const arr = [1, 2, 3, 4, 5];

    for (let i = 0; i < 5; i++) {
       let x = arr[i];
    }

    console.log(x);
}

foo();
bar();

$ node 1.js
5
1

А теперь вынесите-ка let из второго цикла, чтобы память лишнюю не выделять!

function bar() {
    let x = 1;
    const arr = [1, 2, 3, 4, 5];

    let x;
    for (let i = 0; i < 5; i++) {
       x = arr[i];
    }

    console.log(x);
}

$ node 1.js
  1.js:5
    let x;
        ^

SyntaxError: Identifier 'x' has already been declared

т.е. не получится допустить баг, будет показана явная ошибка при запуске, что я и имел в виду

Вот только что именно сделает тот самый гипотетический абсолютно невнимательный человек, который эту ошибку увидит? Использует ли он другое имя для переменной, или просто удалит строку let x;?

нормальный человек использует другую переменную, потому что ошибка максимальна ясна и понятна.
про других я не скажу, может быть всякое.
А вот кейс с var плох тем что var x = something; может назначаться не всегда, а быть еще и завернута в if, который срабатывает только при каких-то редких обстоятельствах, так что код с ошибкой пройдет и ручное тестирование, и автотесты если они не покрывают тот самый редкий if и выстрелит у вас в продакшине. Лично подтверждаю что видел не один такой случай.

Вы сейчас пишете про какой-то загадочный абстрактный код, в то время как обсуждается конкретный бинарный поиск.

я думал мы обсуждаем почему не стоит использовать var, поскольку вы написали "А вот если бы использовали var - такого вопроса бы не стояло."

я сейчас потестировал код предложенный автором на node v14 которая была под рукой. Так вот, если заменить var на let, он работает быстрее.

что касается бинарного поиска, то вот вам мой вариант, он медленнее чем код автора, но наверное если потратить чуть больше времени, можно сделать его быстрее

function find(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
            continue;
        }

        if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            break;
        }

    }

    return result;
}

в общем вот вам код которым и который я тестировал:
отсутствие ошибок и корректность метода тестирования не гарантирую, я просто развлекался в свбодное время

// Orignal version but with bits shift
function fv0(a, x) {
  if (a == null || a.length == 0) return -1;
  var answer = -1;
  var low = 0;
  var high = a.length - 1;

  while(low <= high) {
    var mid = (low + high) >> 1;
    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return answer;
}

// Let's use let instead of var
function fv1(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1

  while(low <= high) {
    let mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// Let's declare mid outside of loop
function fv2(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1
  let mid;

  while(low <= high) {
    mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// My version
function fv3(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
            continue;
        }

        if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            break;
        }

    }

    return result;
}

// Let's test
let a = [];
let t0 = 0;
let t1 = 0;
let t2 = 0;
let t3 = 0;

for (let i = 0; i < 1000000; i++) {
    for (j = 0; j < 1000; j++) {
        a[j] = Math.round(Math.random() * 100);
    }

    a.sort((a, b) => {
        if (a < b) {
            return -1;
        }

        if (a > b) {
            return 1;
        }

        return 0;
    })

    let x = Math.round(Math.random() * 100);

    let startTime = Date.now();
    let r0 = fv0(a, x);
    let endTime = Date.now();
    t0 += (endTime - startTime);

    startTime = Date.now();
    let r1 = fv1(a, x);
    endTime = Date.now();
    t1 += (endTime - startTime);

    startTime = Date.now();
    let r2 = fv2(a, x);
    endTime = Date.now();
    t2 += (endTime - startTime);

    startTime = Date.now();
    let r3 = fv3(a, x);
    endTime = Date.now();
    t3 += (endTime - startTime);

    if (r3 != r0) {
        console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r3);
    }
}

console.log("original version", t0);
console.log("original version with let", t1);
console.log("original version with declared mid outside of the loop", t2);
console.log("my version", t3);


OUTPUT:
original version 83
original version with let 71
original version with declared mid outside of the loop 52
my version 61

немножко переделал свой код:

function fv3(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
        } else if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            return result;
        }
    }

    return result;
}

и прогнал 2000000 итераций для строки размером 2000, в этот раз версия с let внутри цикла, как ни странно, оказалась быстрее всех, первая версия которая приходит в голову это особенности GC

original version 143
original version with let 116
original version with declared mid outside of the loop 123
my version 120

Тут числа от запуска к запуску прыгают чуть ли не в полтора раза, их бесполезно сравнивать.

хорошо, я немного переделал бенчмарк чтобы он работал быстрее и надежнее добавил еще один вариант. Таки получается что var всегда медленнее чем let:

// Orignal version but with bits shift
function fv0(a, x) {
  if (a == null || a.length == 0) return -1;
  var answer = -1;
  var low = 0;
  var high = a.length - 1;

  while(low <= high) {
    var mid = (low + high) >> 1;
    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return answer;
}

// Let's user let instead of var
function fv1(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1

  while(low <= high) {
    let mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// Let's declare mid outside of loop
function fv2(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1
  let mid;

  while(low <= high) {
    mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}


// Let's declare mid outside of loop and initialize it
function fv3(a, x) {
  if (a == null || a.length == 0) return -1;

  let answer = -1;
  let low = 0;
  let high = a.length - 1
  let mid = 0;

  while(low <= high) {
    mid = (low + high) >> 1;

    if (a[mid] == x) {
      return x;
    } else if (a[mid] < x) {
      answer = a[mid];
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return answer;
}

// My version
function fv4(a, x) {
    if (a == null || a.length == 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += ((len - pos) >> 1) || 1;
        } else if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            return result;
        }
    }

    return result;
}

// Let's test
let a = [];
let t0 = 0;
let t1 = 0;
let t2 = 0;
let t3 = 0;
let t4 = 0;

let startTime;
let endTime;

for (j = 0; j < 4096; j++) {
    a[j] = Math.round(Math.random() * 1000);
}

a.sort((a, b) => {
    if (a < b) {
        return -1;
    }

    if (a > b) {
        return 1;
    }

    return 0;
})

for (let i = 0; i < 100000000; i++) {
    let x = Math.round(Math.random() * 1000);

    startTime = Date.now();
    let r0 = fv0(a, x);
    endTime = Date.now();
    t0 += (endTime - startTime);

    startTime = Date.now();
    let r1 = fv1(a, x);
    endTime = Date.now();
    t1 += (endTime - startTime);

    startTime = Date.now();
    let r2 = fv2(a, x);
    endTime = Date.now();
    t2 += (endTime - startTime);

    startTime = Date.now();
    let r3 = fv3(a, x);
    endTime = Date.now();
    t3 += (endTime - startTime);

    startTime = Date.now();
    let r4 = fv4(a, x);
    endTime = Date.now();
    t4 += (endTime - startTime);

    if (r4 != r0) {
        console.error(a.join(','), 'x=' + x, 'author=', r0, 'me=', r4);
    }
}

console.log("original version", t0);
console.log("original version with let", t1);
console.log("original version with declared mid outside of the loop", t2);
console.log("original version with declared and initizalized mid outside of the loop", t3);
console.log("my version", t4);
node 1.js && node 1.js && node 1.js && node 1.js && node 1.js
original version 6730
original version with let 6398
original version with declared mid outside of the loop 6236
original version with declared and initizalized mid outside of the loop 6704
my version 7701
original version 6846
original version with let 6405
original version with declared mid outside of the loop 6326
original version with declared and initizalized mid outside of the loop 6493
my version 7682
original version 7000
original version with let 6448
original version with declared mid outside of the loop 6250
original version with declared and initizalized mid outside of the loop 6497
my version 7528
original version 6988
original version with let 6422
original version with declared mid outside of the loop 6395
original version with declared and initizalized mid outside of the loop 6508
my version 7566
original version 6887
original version with let 6373
original version with declared mid outside of the loop 6310
original version with declared and initizalized mid outside of the loop 6608
my version 7677

2) нет проверки на то что входное значение может быть не только null но и чем угодно, например объектом или строкой

Ну тогда уж надо проверить, что это массив чисел, и что он отсортирован по возрастанию.

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

ну этого не было в условиях задачи.

Как и того, для чего нужен этот массив)

Но там явно указано, что нам дан массив.

А вообще, лучше тогда уж так:

function f(a: Array<number>, x: number): number {
  // ...
}

вообще в последних версиях js есть метод findLast, так что еще один минус автору за изобретение велосипеда. И даже если метода нет, то возможно не стоило выпендриваться, а стоило писать что-то (я не тестировал но кажется должно работать):

const findLastIndex = (array, comparator) => {
    // или любой алгоритм по вкусу
    for (let i = array.length - 1; i >= 0; i--) {
        if (comparator(array[i])) {
            return i;
        }
    }

    return -1;
}

function find(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    const result = a[findLastIndex(a, i => i <= x)];
    return result == undefined ? -1 : result;
}

findLast - O(n).

а вот это действительно печально.


Вот версия для всех случаев, сложность O(log N), точнее кажется O(log2 N) поскольку мы ищем строго первый или последний элемент в массиве в котором значения могут повторяться, в оригнальном алгоритме который автор видимо списал из википедии ищеться первое попавшеся значение, поэтому там действительно O(log N)

// arr: An array that must be sorted in ascending order.
// cmp: A comparator function(a) or a target value. 
//
// The comparator function should be defined to take a single argument 'a'
// and compare it internally:
//    It should return -1 if 'a' is less than a reference value;
//    It should return  0 if 'a' is equal to a reference value;
//    It should return  1 if 'a' is greater than a reference value;
//
// If 'cmp' is not a function, it is treated as a target value against
// which elements of 'arr' are compared.

function createComparator(x) {
	return function(a) {
		if (a < x) {
			return -1;
		}

		if (a > x) {
			return 1;
		}

		return 0;
	}
};

function _getComparator(arg) {
	if (typeof arg === 'function') {
		return arg;
	}

	return createComparator(arg);
}

function findLastIndexEqual(arr, cmp) {
	cmp = _getComparator(cmp);

	let len = arr.length;
	let pos = len >> 1;
	let result = -1;
	let start = 0;

	while (pos >= start && pos < len) {
		if (cmp(arr[pos]) === 0) {
			result = start = pos;
			pos += (len - pos) >> 1 || 1;
		} else if (cmp(arr[pos]) > 0) {
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		} else {
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

function findLastIndexLessOrEqual(arr, cmp) {
	cmp = _getComparator(cmp);

	let len = arr.length;
	let pos = len >> 1;
	let result = -1;
	let start = 0;

	while (pos >= start && pos < len) {
		if (cmp(arr[pos]) <= 0) {
			result = start = pos;
			pos += (len - pos) >> 1 || 1;
		} else {
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		}
	}

	return result;
}

function findLastIndexLess(arr, cmp) {
	cmp = _getComparator(cmp);

	let len = arr.length;
	let pos = len >> 1;
	let result = -1;
	let start = 0;

	while (pos >= start && pos < len) {
		if (cmp(arr[pos]) < 0) {
			result = start = pos;
			pos += (len - pos) >> 1 || 1;
		} else {
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		}
	}

	return result;
}

function findFirstIndexEqual(arr, cmp) {
	cmp = _getComparator(cmp);

	let len = arr.length;
	let pos = len >> 1;
	let result = -1;
	let start = 0;

	while (pos >= start && pos < len) {
		if (cmp(arr[pos]) === 0) {
			result = pos;
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		} else if (cmp(arr[pos]) > 0) {
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		} else {
			start = pos;
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

function findFirstIndexGreaterOrEqual(arr, cmp) {
	cmp = _getComparator(cmp);

	let len = arr.length;
	let pos = len >> 1;
	let result = -1;
	let start = 0;

	while (pos >= start && pos < len) {
		if (cmp(arr[pos]) >= 0) {
			result = pos;
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		} else {
			start = pos;
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

function findFirstIndexGreater(arr, cmp) {
	cmp = _getComparator(cmp);

	let len = arr.length;
	let pos = len >> 1;
	let result = -1;
	let start = 0;

	while (pos >= start && pos < len) {
		if (cmp(arr[pos]) > 0) {
			result = pos;
			len = pos;
			pos = start + (((pos - start) >> 1) || pos - 1);
		} else {
			start = pos;
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

Если оно O(n), никто не мешает закодить нечто вроде такого, у меня это заняло два часа. Нужно еще два часа потратить чтобы убрать лишние итерации, но мне честно говоря лень. Но факт то что написать бинарный поиск с компараторами это не проблема. Использовать с осторожностью, тестировал каждый кейс на рандомных строках длинной 400 символов со значениям [0..99] и рандомных значениях x в тех же пределах, в качестве эталона использовал простейший перебор, для каждого кейса делал 1 000 000 итераций, вроде ошибок не нашлось.

// Array must be sorted in asending order
// Comparator must return:
//    < 0 if value less than expected;
//      0 if value is equal to excepted
//    > 0 if value is greater than expected

function findLastIndexEqual(arr, cmp) {
	let len = arr.length;
	let pos = len >> 1;
	let result = -1;

	while (pos > -1 && pos < len) {
		if (cmp(arr[pos]) === 0) {
			result = pos;
			pos += (len - pos) >> 1 || 1;
		} else if (cmp(arr[pos]) > 0) {
			len = pos;
			pos = pos >> 1 || pos - 1;
		} else {
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

function findLastIndexLessOrEqual(arr, cmp) {
	let len = arr.length;
	let pos = len >> 1;
	let result = -1;

	while (pos > -1 && pos < len) {
		if (cmp(arr[pos]) <= 0) {
			result = pos;
			pos += (len - pos) >> 1 || 1;
		} else {
			len = pos;
			pos = pos >> 1 || pos - 1;
		}
	}

	return result;
}

function findLastIndexLess(arr, cmp) {
	let len = arr.length;
	let pos = len >> 1;
	let result = -1;

	while (pos > -1 && pos < len) {
		if (cmp(arr[pos]) < 0) {
			result = pos;
			pos += (len - pos) >> 1 || 1;
		} else {
			len = pos;
			pos = pos >> 1 || pos - 1;
		}
	}

	return result;
}

function findFirstIndexEqual(arr, cmp) {
	let len = arr.length;
	let pos = len >> 1;
	let result = -1;

	while (pos > -1 && pos < len) {
		if (cmp(arr[pos]) === 0) {
			result = pos;
			len = pos;
			pos = pos >> 1 || pos - 1;
		} else if (cmp(arr[pos]) > 0) {
			len = pos;
			pos = pos >> 1 || pos - 1;
		} else {
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

function findFirstIndexGreaterOrEqual(arr, cmp) {
	let len = arr.length;
	let pos = len >> 1;
	let result = -1;

	while (pos > -1 && pos < len) {
		if (cmp(arr[pos]) >= 0) {
			result = pos;
			len = pos;
			pos = pos >> 1 || pos - 1;
		} else {
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}

function findFirstIndexGreater(arr, cmp) {
	let len = arr.length;
	let pos = len >> 1;
	let result = -1;

	while (pos > -1 && pos < len) {
		if (cmp(arr[pos]) > 0) {
			result = pos;
			len = pos;
			pos = pos >> 1 || pos - 1;
		} else {
			pos += (len - pos) >> 1 || 1;
		}
	}

	return result;
}


function createComparator(x) {
	return function(a) {
		if (a < x) {
			return -1;
		}

		if (a > x) {
			return 1;
		}

		return 0;
	}
};

a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];

console.log(a[findLastIndexLessOrEqual(a, createComparator(12))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(13))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(2))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(22))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(3))]);
console.log(a[findLastIndexLessOrEqual(a, createComparator(21))]);

в этом году даже пришлось стандарт править чтобы у браузеров появился шанс это замедление убрать.

Расскажите подробней?

Так, я ошибся, стандарт ещё не правили. Но собираются.

Это из сентябрьского митинга TC39: презентация, протокол

Summary

  • Years after ES6, let and const still commonly cause performance regressions vs var, and transpilers do not implement TDZ. The result is that let and const are avoided in shipped JS code.

  • Generally, if the committee cares about its features being adoptable, these sorts of 5+-year retrospectives will be important.

  • SYG proposes treating some or all cases of TDZ as simply evaluating to undefined, as var does.

  • Most of the committee agreed with the goal of ensuring that features like this are adoptable in practice, but there was no consensus on whether semantics changes to support that are needed.

Conclusion

A proposal may be formed on this topic in the future

Если я правильно понял, то это касается только не инициализованных значений объявленных с помощью let?

Напрямую это касается переменных, объявленных через let посреди блока, но использованных в замыкании до этого момента:

const fn = () => console.log(x);
// fn() - ошибка
let x = 5;
fn(); // а так нормально

Но вот сама возможность подобного обращения и необходимость её отслеживать может повлиять хоть вообще на все переменные, тут всё зависит от глупости оптимизатора.

и на этом основании вы выше посоветовали не использовать let вместо var?

На этом основании я посоветовал не спешить переписывать все var на let.

ну потестируйте код автора сами с var и let, и скажите есть там проблемы с производительность в случае let? Я вот потестировал не нашел никаких проблем. Также я вам объяснил почему var лучше не использовать и даже ссылки дал на материалы по этому поводу, а вы даже отвечать не стали. Судя по всему в жизни вы человек крайне не приятный и мне чет стало совсем неприятно с вами общаться. На этом прощаюсь и желаю вам поумнеть и стать добрее.

Вот тут вы правы, Math.floor - тяжёлая операция, не фиг её делать лишний раз.

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

Чтобы переполнить number - нужен массив, занимающий 32 петабайта памяти. Я не верю в такие массивы.

А, я понял о чём вы.

p.s не сразу понял что под простейшей реализацией автор все таки имел в виду двоичный поиск. и также не сразу понял что перевод. также я я не имел в виду что мое решение лучше, я его написал до того как прочитал код в качестве начального варианта который должен быть быстрее простого перебора.

Если бы я дальше работал бы над кодом то разумеется получился бы бинарый поиск

и получилось бы в итоге у меня что-то типа такого:

function find(a, x) {
    if (!Array.isArray(a) || a.length === 0) {
        return -1;
    }

    let result = -1;
    let len = a.length;
    let pos = len >> 1;

    while (pos < len) {
        if (a[pos] == x) {
            return x;
        }

        if (a[pos] < x) {
            result = a[pos];
            pos += (len - pos) >> 1 || 1;
            continue;
        }

        if (pos > 0) {
            len = pos;
            pos >>= 1;
        } else {
            break;
        }

    }

    return result;
}

Этот алгоритм попросту неправильный, вы теряете левую границу и в итоге делаете лишние итерации.

мне кажется вы ошибаетесь, посмотрите пожалуйста вот этот мой коммент https://habr.com/ru/companies/ispsystem/articles/779224/comments/#comment_26245396 - я там в сравниваю результаты на рандомных данных с результатами оригинального алгоритма предложенного автором, расхождений в результатах функции не выявляется

Если вы считаете что алгоритм таки неверный, предложите тесткейс который это докажет. Если все так как вы говорите, это должно быть легко

понял о чем вы, действительно там есть лишние итерации

или например вот так тоже неплохо

function fv4o(a, x) {
    let result = -1;
    let end = (a || []).length;
    let start = 0;
    let pos = end >> 1;

    while (pos < end && result != x) {
        if (a[pos] > x) {
            end = pos;
            pos = ((end - start) >> 1) + start;
            continue;
        }

        result = a[pos];
        start = pos;
        pos = ((end - start) >> 1 || 1) + start;
    }

    return result;
}

ок, таки нашел время и сделал версию которая меня вроде устраивает, но еще можно поработать и оптимизировать

function fv4o(a, x) {
    if (a == null || a.length == 0) {
        return -1;
    }

    let result = -1;
    let end = a.length;
    let start = 0;
    let pos = end >> 1; // Relative position
    let abspos = pos; // Absolute position
    let item = 0;

    while (abspos < end) {
        item = a[abspos];

        if (item == x) {
            return x;
        }

        if (item <= x) {
            result = item;
            start = abspos;
        } else {
            end = abspos;
        }

        pos = (end - start) >> 1 || 1;
        abspos = pos + start;
    }

    return result;
}


Поскольку практически все ваши “претензии” автору основаны на ваших же вкусовых предпочтениях, я не буду устраивать критику этой “критике”, это пустое. Но о том, что бросилось в глаза, таки спрошу:

// а что если здесь не массив а объект?

Возьмём в качестве примера код, который используется буквально везде — стандартную библиотеку C. Выбирайте на свой вкус, самые популярные — BSD libc, GNU glibc, musl. Загляните в исходный код практически любой функции модуля string.h.

Вот несколько примеров:
char *
strcat(char * __restrict s, const char * __restrict append)
{
        char *save = s;

        for (; *s; ++s);
        while ((*s++ = *append++));
        return(save);
}

int
strcmp(const char *s1, const char *s2)
{
        while (*s1 == *s2++)
                if (*s1++ == '\0')
                        return (0);
        return (*(const unsigned char *)s1 - *(const unsigned char *)(s2 - 1));
}

char *
strdup(const char *str)
{
        size_t len;
        char *copy;

        len = strlen(str) + 1;
        if ((copy = malloc(len)) == NULL)
                return (NULL);
        memcpy(copy, str, len);
        return (copy);
}

Не смущает, что нигде не проверяется, являются ли “строками” входящие “строки”? Если хотите, могу очень доступно объяснить, почему не проверяется.

А в вашем коде я вижу одну из причин того, почему многие современные приложения такие “тяжёлые”, веб-страницы с тремя параграфами текста и парой кнопок грузят свои десятки мегабайт по несколько секунд, и прочий code bloating. Ваш код делает работу, которая никому не нужна, которой не было в ТЗ, вы не делаете отличий между generic-кодом и частным случаем, вы возводите свои весьма поверхностные представления о безопасности кода в безумный абсолют “все параметры всех функции должны быть проверены на всё”.

В итоге я бы вас не взял с таким решением

я пока не опубликовал финальное решение. то что в посте указано то что входной параметр массив или null я не заметил, это довольно странное условие в случае js. Но кстати его код проверяет еще и на undefined не очевидным образом, чего не было в условиях задачи. По поводу libc я не скажу что это хороший код, там много трэша. Вот посморите на getaddrinfo, https://codebrowser.dev/glibc/glibc/sysdeps/posix/getaddrinfo.c.html, разве это похоже на хороший код? Но даже там условия и циклы часто отбиты.

По поводу

if (foo ) {
}
явные начало и конец блока лучше чем не явные, читать проще и меньше ошибок в итоге

А теперь сравните с кодом из скажем ZFS https://github.com/openzfs/zfs/blob/master/module/avl/avl.c

По поводу кода предложенного автором - там вообще нет ни одной отбивки, все единым блоком кода. То есть явные проблемы с читаемостью. Даже в ваших примерах из glibc есть отбивки

и вообще разве отбивки это основное? Там блин var!!! и Math.floor!!!. Этого уже достаточно кмк

Вот вам мой допиленный вариант:

function fv4o(a, x) {
    if (a == null || a.length == 0) {
        return -1;
    }

    let result = -1;
    let end = a.length;
    let start = 0;
    let relpos = end >> 1; // Relative cursor position from start
    let abspos = relpos;   // Absolute cursor position
    let item;

    while (abspos < end) {
        item = a[abspos];

        if (item == x) {
            return x;
        }

        if (item <= x) {
            result = item;
            start = abspos;
        } else {
            end = abspos;
        }

        relpos = (end - start) >> 1 || 1;
        abspos = relpos + start;
    }

    return result;
}

ну вот вам еще такое решение


function fv4o(a, x) {
    let result = -1;
    let end = (a || []).length;
    let start = 0;
    let pos = end >> 1;

    while (pos < end && result != x) {
        if (a[pos] > x) {
            end = pos;
            pos = ((end - start) >> 1) + start;
            continue;
        }

        result = a[pos];
        start = pos;
        pos = ((end - start) >> 1 || 1) + start;
    }

    return result;
}

}

Не смущает, что нигде не проверяется, являются ли “строками” входящие “строки”?

А как это вообще проверить в C?

Для начала дай определение для “строка” (или возьми в стандарте :)). Чтобы продолжать разговор об этом, необходимо убедиться, что мы имеем в виду одно и то же.

НО!

Ты не на то обращаешь внимание. Я видел слишком много неофитов, которые считают, что тут надо проверять хотя бы на NULL. Не надо!

Ну пример то так себе - сколько прописей памяти это породило. Всякие Rust не просто так появились.

нафига тут else если перед ним return?

А если однажды код изменится и там будет не return? Если одно условие должно исключать другое, лучше "пере", чем "недо".

Конечно, я не про конкретно этот случай с простым условием, а вообще.

// Нафига Math.floor? Битовый сдвиг проще: (low + high) >> 1

А разве low + high тут в общем случае не могут вылезти за пределы int32?

тут вы правы.
js он реально местами странноватый

4294967290 + 4294967295
8589934585 // переполнения нет
4294967290 >> 1
-3 // переполнение есть

но как оказывается есть специальные битовые операторы о которых я не был в курсе >>> и <<<:

(4294967290 + 4294967290) >>> 1
2147483642

что тоже как ни странно дает неправильный результат.
Вот так вроде ок

(4294967290>>>1) + (4294967290>>>1)

Так вы потеряли единицу при сложении нечётных чисел.

И если на больших числах эта единица ни на что не влияет, то вот при попытке найти середину между 1 и 3 у вас получается 1. А серединой между 1 и 1 и вовсе оказывается 0, хорошо хоть при тройных ветвлениях такая середина никогда не вычисляется.

Правильная формула приведена в статье, её только поправить надо:

low + (high — low) >>> 1;

Оператор >>> тоже даёт переполнение. Присмотритесь внимательнее, разве похоже число 2147483642 на середину между 4294967290 и 4294967290?

Вся разница в том, что >> интерпретирует левый операнд как знаковый, а >>> - как беззнаковый. Кстати, они этот оператор не придумали, а взяли из Java.

Штука в том что вообще number - это 64-битовое число с плавающей точкой, но для побитовых операций он приводится к int32. Т.е. целочисленное деление на 2 побитовым сдвигом возможно без потерь только если делимое (его целая часть) влезает в 32 бита.
Согласно спекам array.length является uint32, тогда выходит сумма двух индексов массива может выйти за 32 бита.
Я бы использовал Math.trunc((low + high) / 2 ), в статье используется Math.floor что для положительного числа даст тот же результат (индексы же - значит положительное), но по-моему это хуже с точки зрения семантики .

Исходя из посталвенных условий это скорее задача для определения нахождления кандидата на 1 волне с вами и угадывает ли он что вы от него хотите.

Я в другом подобном обсуждении уже писал, что когда у вас, как у FAANG, за воротами очередь кандидатов стоит и когда у вас десятки тысяч сотрудников - можно позволить себе отбирать тех, на одной волне с командой. А потом уже смотреть как они код писать умеют.

В итоге собрать гомогенную команду в которой все радостно думают одинаково, совершают одинаковые ошибки, и не способны их друг у друга заметить. Все получают триста какосеков, а сайты с текстом и двумя картинками потом грузятся по 7 секунд.

Пока это не влияет на бизнес - нет проблемы (ну кроме как для пользователей). А у гугла бизнес идет хорошо т.к. они заняли определенную нишу и по факту никто туда уже влезть не может. А свежие идеи они покупают вместе с командами. Т.е. изнутри инновации не особо нужны.

Бизнес гугла настолько большой, что им уже нет разницы, ничего из разработки не будет на него влиять в короткой перспективе. Если они уволят всех разрабов и наймут курицу с отрубленной головой которая бегает по клавиатуре, бизнес будет приносить прибыль еще очень долго.

Что, возвращаясь к топику, не добавляет уверенности в том что их рекрутерские практики хороши и их надо копировать.

Я это и имел в виду.

Порой, по разным причинам, мы получаем друг от друга ложные или неточные сигналы.

И далее по тексту выясняется, что от интервьюера все сигналы по умолчанию кошерные, а не прав может быть только кандидат.

Тут многие в примерах смело используют функцию вычисления длины массива, но в некоторых языках это уже просмотр всего массива.

НЛО прилетело и опубликовало эту надпись здесь

В сях массив таки придется весь пройти, чтобы длину получить. И тогда бинарный поиск тут уже будет бесполезен, как и сам факт отсортированности массива.

Это только если массив нуль-терминированный или вроде того.

А обычно эта длина передаётся дополнительным параметром.

Про то и все посты, что для профи задача некорректная

Так что тут некорректного-то?

прежде всего некорректный здесь вы, потому что выше убеждаете людей что var лучше чем let, потому что в некоторых случаях оно медленнее, чем сразу выдаете в себе дилетанта лол

Тогда это уже не массив. Это или нуль-терминэйтед стринг или связный список или еще что-то, но не массив.

В С как раз массив так и хранят как нуль-терминетед последовательность указателей. Иногда. Но можно и не так.

Но если часто что-то сортировать, то наверно лучше хранить в дереве или еще как. И тогда задачка станет совсем другой. ))

Я всегда думал что в С массив это указатель на первый элемент. И никаких нуль терминетед и в помине нет, что malloc выдаст так и будет.

Вы со строками путаете. Нет никаких нул-терминаторов в массиве. Даже если у вас двумерный массив указателями на указатели - передают везде размер массива.

Чем должен оканчиваться массив интов в вашем представлении? Хуем моржовым?

Зачем вы продолжаете спорить о том, в чём явно не разбираетесь?

int result = a.LastOrDefault(n => n < x);

if (result == 0) result = -1;

return result

Кажется, я уложился в 30 строчек.

Делать сходу двоичный поиск, без требований - это признак незрелости программиста. Premature optimization.

Оптимизация делается ТОЛЬКО по результатам замеров и профилирования. Иначе алгоритмы усложняются и код становится нечитаемым. А читаемость кода для львиной части кода гораздо важнее скорости.

Можно даже в одну строку (плюс корректная обработка нулей в исходном массиве).

a.LastOrDefault(n => n <= x, -1);

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

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

Только вот двоичный поиск редко когда требует больше записей в кеше чем поиск линейный, так что если он и окажется медленнее - то уж точно не из-за кеша.

Зато двоичный поиск генерирует кэш промахи и сбивает логику префетчинга, а на этом часто весь перформанс и умирает. Подобное надо бенчить на конкретных продовых данных.

Кеш-промахи и префетчинг тут точно ни при чём.

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

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

Есть же branch-free реализации бин-поиска. Даже тут на хабре статью видел как-то.

Вы про тернарный оператор вместо if?

Нет. Суть в том, что размер отрезка каждый раз делиться на 2, а вот начало смещается в середину или нет в зависимости от условия. Можно математическую формулу с умножением на bool делать, можно выбирать значение из массива по индексу 0 или 1. Но это не особо эффективно будет, хоть ветвлений и нет. Самое быстрое - заставить компилятор какой-нибудь cmov использовать.

Подобное надо бенчить на конкретных продовых данных

Боюсь не получится найти такие данные, где binary search проиграет. Разве что если там 3-5 элементов в массиве.

Если массив целиком влезает в кеши, да даже если и не целиком, то вполне может оказаться что перебор отрабатывает быстрее двоичного поиска, который будет постоянно сбрасывать кеш если данных много

У вас нестыковка в суждении.

На маленьких массивах рулит обычный перебор из-за простоты тела цикла и из-за спекулятивных вычислений. На больших рулит логарифмическая асимптотика. А кэш может склонить чашу весов только на пограничных объёмах, если они окажутся больше размера кэша (что вряд ли возможно для данной задачи на современных процессорах).

Ещё большую роль играет сочетание двух вещей: необходиомость сортировки перед поиском и предполагаемое число поисков. Если сортировать надо, и число запросов невелико, то даже на больших объёмах данных гораздо быстрее будет нужное количество раз линейно поискать (бонусом, простые данные типа чисел очень сильно ускоряются векторными инструкциями).

Двоичный поиск быстрее уже при 4-5 элементах в массиве.

В общем хоть меня и удивляет популярность такой достаточно простой задачи, но я сначала дошел до условия, решил задачку, а потом продолжил читать. Не думал, что мое наивное решение и будет тем самым, которое ожидает автор статьи. Но хочу показать свое решение в коментах, так как оно оригинально тем, что сделано на WL:

f[arr : {a1_Integer, ___Integer}, x_Integer, default_Integer : -1] /; x < a1 := default

f[arr : {___Integer, an_Integer}, x_Integer, default_Integer : -1] /; x >= an := an

f[arr : {__Integer}, x_Integer, default_Integer : -1] := 
With[{halfLen = Round[Length[arr]/2]}, 
  If[arr[[halfLen]] < x, 
    f[arr[[halfLen + 1 ;; ]], x, arr[[halfLen]]], 
    f[arr[[ ;; halfLen]], x, default]
  ]
]

f::argex = "Argument exception"; 

f[args___] := (Message[f::argex]; Defer[f[args]])

На скриншоте код и результаты тестов. Результаты не уместились, но тестов больше чем в самой статье, т.е. они те же самые, а еще включают то, что не было учтено.

Тоже подумал сразу про что-то в роде паттерн-матчинг)

__Integer & args___

Какой замечательный язык. У этих ___ (3 штуки аж) есть какая-то история?

Да, конечно. Это такой синтаксис шаблонов/паттернов/образцов в WL. Во многих языках программирования, в которых есть паттерн-матчинг есть такая штука как wildcard. То есть "_". Так вот в WL шаблоны могут состоять из разных вариаций wildcard. Вот несколько примеров. Сравнение происходит при помощи функции MatchQ[expression, pattern]:

MatchQ[x, _] == True (*одиночное подчеркивание - все что угодно*)
MatchQ[f[x], f[_]] == True (*это значит выражение слева это f с любым аргументом*)
MatchQ[f[x, y], f[_]] == False
MatchQ[f[], f[_]] == False

MatchQ[f[1, 2, 3, 4], f[__]] == True (*два подчеркивания от одного до бесконечности элементов*)
MatchQ[f[], f[__]] == False

MatchQ[f[], f[___]] == True
MatchQ[f[x], f[___]] == True
MatchQ[f[x, y, z], f[___]] == True (*три подчеркивания любое число элементов от 0 до беконечности*)

Кроме трех вариантов wildcard есть еще возможность указывать диапазон количества элементов или конкретное значение, но это я оставлю на потом. И так мы рассмотрели возможность матчить произвольное выражение с шаблоном, который соответствует одному "чему угодно", одному и более или нулю и более штук "чего угодно". Но что если я хочу чтобы это было не что угодно, а только выражения/объекты с определенными типами? Тогда после подчеркивания я могу напрямую указать этот тип. Как понять какой тип у выражения в языке с динамической типизацией? При помощи функции Head. Это значит что

Head[1] == Integer
Head[1.0] == Real
Head[1/3] == Rational
Head[1 + I] == Complex
Head["string"] == String
Head[x] == Symbol
Head[f[x]] == f
Head[f[x][y][z]] == f[x][y]
Head[Head[f[x][y][z]]] == f[x]

И я могу взять любой результат, который возвращает Head и вставить его сразу после одного/двух/трех символов подчеркивания. То есть вот так:

MatchQ[1, _Integer] == True
MatchQ[1.5, _Integer] == False

То есть это wildcard с проверкой типов, но не все так просто.

Вот например как можно проверить что у нас массив только целых:

MatchQ[{1, 2, 3, 4}, {__Integer}] == True

А вот так я могу проверить, что у меня есть массив где сначала идут целы числа, потом рациональные, а потом комплексные. При этом комплексных может не быть совсем

MatchQ[{1, 2, 3, 1/3, 1/5, 1/7, I, I/3}, {__Integer, __Ratonal, ___Complex}] == True
MatchQ[{1, 2, 1/5}, {__Integer, __Ratonal, ___Complex}] == True

А еще wildcard можно связать с именем вот так:

MatchQ[f[1], f[x_]] == True

В MatchQ это бесполезно, но в функции, которая вытаскивает что-то по шаблону - это полезно:

Cases[{f[1]}, f[x_] :> x] (* => {1} *)

Т.е. выше я связал значение 1 из выражения с символом x и смог извлечь это значение. Если использовать несколько подчеркиваний, то будет вот так:

Cases[{f[1, 2, 4]}, f[x__] :> {x}] (* => {{1, 2, 4}}*)

Это небольшая часть паттерн матчинга в WL но нам пока достаточно. Теперь перейдем к главному - шаблоны можно использовать в в определениях функций, т.е. создав функцию вот так:

f[x_] := x + 1

Я говорю математике о том, что как только она встречает выражение, которое матчится с:

MatchQ[f[1], f[x_]] == True

То сразу же происходит замена на правую часть определения функции - т.е. на x + 1. Определив так функция - я отсекаю все шаблоны, которые не матчатся с шаблоном f[x_]. Вызвав функцию на том, что не матчится ни с одним из шаблонов, которые были определены - ядро WL вернет результат ввода как есть. Т.е. например:

f[x_, y_] := x + y

f[1, 2, 3] (* => f[1, 2, 3] без изменений*)

Ну и возвращаясь к примеру из моего комментария выше шаблон

f[arr: {a1_Integer, ___Integer}, x_Integer] /; x < a1 := ...

Означает, что функция определена только на последовательности аргументов, которая представляет из себя:

  1. Первый аргумент список, где первый элемент списка обязательно целое число, а дальше может быть от нуля до бесконечности только целы чисел. Но я не стал писать a__Integer, чтобы связать ТОЛЬКО первый элемент списка с переменной a1, а не всю последовательность.

  2. Второй аргумент - просто целое число.

  3. После знака /; идет условие, которое может использовать связанные переменные

Если у вас возникнут вопросы после моего объяснения или я объяснил слишком запутанно - то напишите пожалуйста, я готов ответить на любые вопросы!

Спасибо за такой развёрнутый ответ (лови плюс в карму). Я думал это просто дичь уровня "исторически так получилось, что разные пласты костылей наложились друг на друга", а тут целая механика чего-то вроде variadic arguments в Typescript, только на стероидах.

Спасибо большое за оценку моих трудов =)
Кстати мой любимый книжный пример - это сортировка пузырьком при помощи шаблонов:

{5, 4, 2, 6, 3, 2} //. 
   {fst___, x_Integer, y_Integer, rst___} :> 
     {fst, y, x, rst} /; x > y
  • //. - сокращение для ReplaceRepeated - функция которая выполняет повторяющуюся замену

  • :> - правило замены

  • /; - дополнительное условие для замены, но не обязательное

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

MatchQ[{5, 4, 2, 6, 3, 2}, {fst___, x_Integer, y_Integer, rst___}] /; x > y

связываются fst = <ничего>; x = 5; y = 4; rst = 2, 6, 3, 2. Оказывается что 5 > 4, тогда условие выполнено и на место исходного списка вставляется:

{fst = <ничего>, y = 4, x = 5, rst = 2, 6, 3, 2} == {4, 5, 3, 6, 3, 2}

Далее этот процесс повторяется, но теперь первый и второй элемент не проходят условие и происходит новое связывание: fst = 4; x = 5; y = 2; rst = 6, 3, 2 и т.д. пока не окажется так, что заменять ничего.

А с чего автор решил, что двоичный поиск будет быстрее, чем векторные SIMD инструкции? К тому же даже с двухканальным доступом к памяти, не говоря уже о четырехканальном, считать такой массив последовательно будет быстрее, чем прыгать по нему двоичным поиском.

А код на Javascript точно сможет задействовать векторные SIMD инструкции?

Кажется нет, можно только если через WASM достучаться до SIMD, лет 10 назад был пропосал на SIMD расширение, но его вскоре выпилили.

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

А причём тут WASM? Речь-то шла про поиск в обычном массиве Javascript.

JS - это язык. А чем и куда он компилируется Вы не указали. Значит для Вас это значение не имеет. Вот и компилируйте, например, в WASM, если хотите поддержку SIMD инструкций. К тому же я Вам предложил альтернативу в виде Tensorflow, которая уж точно SIMD использует.

Понятно, что на ESP32 не только JS, но даже C/C++ SIMD инструкции использовать никакой компилятор не станет. Потому что там их просто нет )

Вот я и не пойму, чего Вы хотите. Машинные инструкции возникают только после компиляции. От языка же их использование не зависит вообще - только от компилятора.

Приведите хоть один компилятор JS, способный задействовать SIMD-инструкции в простом цикле линейного поиска по массиву.

А пока вы не привели такого примера - ваш комментарий выглядит полной чушью.

Во-первых, компиляторов JS просто не существует, максимум есть JIT.

Во-вторых, нет абсолютно никакого смысла компилировать JS в WASM. WASM - это технология, позволяющая исполняться коду на разных языках в браузерах, но JS браузеры умеют исполнять и без неё.

В-третьих, чтобы задействовать SIMD-инструкции, нужно как минимум обеспечить гомогенность массива (что уже сложно в JS), а дальше нужно использовать либо явные языковые интринсики (которых в JS нет), либо автовекторизацию (про которую я в JS ни разу не слышал).

компиляторов JS просто не существует

нет абсолютно никакого смысла компилировать JS в WASM.

У Вас раздвоение личности? Мало того, что пишете от том, что нет смысла компилировать тем, чего не существует, так еще и хотите использование SIMD - но не хотите один из вариантов, когда они будут использованы. )))

как минимум обеспечить гомогенность массива

Или, как я написал изначально, воспользоваться TensorFlow. Если бы Вы эту фразу сумели прочитать, то поняли бы, что в этом случае массив будет хранится в формате вектора TF, пригодного к обработке не только SIMD, но и GPU

компиляторов JS просто не существует, максимум есть JIT

Node.js как раз и обеспечивает высокую производительность, благодаря компиляции напрямую в машинный код средствами V8.

НЛО прилетело и опубликовало эту надпись здесь

Вы заблуждаетесь. V8 не использует при исполнении JS-программ байт-код или любой промежуточный код.

Это даже на Хабре подробно рассматривалось.

НЛО прилетело и опубликовало эту надпись здесь

Если хотите изменить общепринятую терминологию, то рекомендую начинать не здесь, а, например, с обсуждения в Википедии:

"JIT-компиляция — технология увеличения производительности программных систем, использующих байт-код, путём компиляции байт-кода в машинный код или в другой формат непосредственно во время работы программы.

НЛО прилетело и опубликовало эту надпись здесь

Я не тычу, а указываю, что Википедия намного лучше адаптирована для фиксации и смены общепринятых терминологий, чем Хабр. И как только Ваше предложение будет там принято, я тоже его стану придерживаться. А до тех пор, простите, придерживайтесь общепринятой терминологии Вы.

НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь

Вы путаете использование промежуточного байт-кода при компиляции, как в LLVM или V8, и интерпретацию байт-кода (JIT).

НЛО прилетело и опубликовало эту надпись здесь

Ладно, убедили, что в некоторых случаях пр