Это псевдокод или какой-то конкретный язык с его особенностями?

да

Тогда ответ на твой вопрос - тоже да.

l - это нижняя граница? Чему она может быть равна? А то l < r && r == 0 на первом шаге как-то смущают.

это лисп же

союз «а» не союз «да»

вопрос собственно:

как лёгким размышлением переходит из очевидного тернарного варианта к менее очевидному[лично мне] асимметричному бинарному?.

Точно, как я не заметил :)

союз «а» не союз «да»

Что? Там или.

Я не понимаю вопроса, прости.

парное присвоение . в обоих случаях l нижняя

r верхняя(в первом в последовательности, во втором сразу после)

r==0 в начале возможно только при n<=0

Сплошной линукс.

у инви. понятно что у него в смысле ислючающего.

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

это псевдокод по мотивам golang и непомня синтаксиса его cond-аналога.

Ну так вот эти две строчки:

1 l,r=0,n
2   while(l<r){

Говорят о том, что в цикл не попасть, не?

у инви. понятно что у него в смысле ислючающего.

«Это А или Б» -> «Да» - это бессмыслица.

что мой псевдокод гарантированно никто уже не реализовал

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

если псевдокод, то не ясно зачем нужен вообще второй вариант, если он «не работает», ведь если ничего найдено не будет, он вернёт произвольное r в интервале [0,n-1].

Говорят о том, что в цикл не попасть, не?

не, там типа присвоение по порядку, l = 1, r = n (иначе не имеет смысла, да)

союз «a» в стартовом топике как противопоставление двух вариантов.

союз «да» используется в стилизациях в роли союза противопоставления.

союз «или» в разговорной речи может быть как включающим так и исключающим.

да. в цикл не попасть если n<=0 ибо lv1,vl2=rv1,rv2 есть синхроное присвоение «place in memory[key:lv1] value of rv1 and in memory[key:lv2] value rv2»

вопрос собственно как имея для себя общеочевидное тернарное решение с лёгкостью восстанавливать асимметричное бинарное.

вложенный if

ох щи. понятно что вместо (cond ((< z 0)...)((== z 0)...)((> z 0) ...))

можно if(z<0)... else if(z==0)... else if(z>0)....

речь про облегчение мысленного перехода к if(u)...else if(!u)... где две из 3 веток преведены к одному виду путём нарушения симметрии тернарного случая сдвигом одной из границ и включения медианы в одну из альтернатив.

цикл {
if > , aaa, continue;
if < , bbb, continue;
ccc;
}

и анониму.

да не проблема как 3 ветки уложить.

проблема как из 3 очевидных альтернатив формулировать равномощный(т.е охватывающий все те же случаи ) 2ух альтернативный.

Ну как-нибудь так, но суть от этого не меняется, без вложенного if никак: ты берёшь один из трёх случаев, проверяешь, да/нет, если нет, то у тебя остаётся ещё два случая.

c = cmp(key,v[m]))
cmp(c, 0):
  r=m
  l=r
sign(c):
 -1:r=m
  1:l=m+1;

извини вынужден по буквам

есть 3 путевой алго < = >

а есть двухпутевой <= > либо !> > либо ещё какой где случай == тем или иным путём «уоднородивают» с одним из строгих неравенств.

и вот в этом и вопрос

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

l = -1
r = n

while (r - l > 1) {
   m = l + (r - l) / 2
   if (a[m] < val)
      l = m
   else
      r = m
}

return r

Это называется lower_bound — первый элемент не меньше данного Если заменить < на <=, получится upper_bound — первый элемент больше данного

Только ты можешь превратить тему бинарного поиска с понятным кодом на C в непонятное месиво псевдокода и твоих объяснений.

Для чего тебе нужен бинарный писк? Для каких данных - опиши, я тебе напишу нормальный «поиск», а не говно, что писали анскилледы выше.

А ещё лучше - напиши свой вариант на сишке и скажи мне - во сколько раз я должен твоё говно слить.

данные в 0..n-1?

слу . вопрос не в том какая молитва правильная.

вопрос как имея очевидное(т.е получаемое из общих сооброжаний) решение через < = > ( c тем недостатком , что если искомое в нескольких экземлярах то ответ первое попавшееся) получить например твой код - какие соображения достоточно помнить , что бы востановить твоё решение.

мне нужно как можно очевидное преобразование из 3 путевого выбора в бинарный.

Запомнить надо один факт: хотим правую границу диапазона — берем <, хотим левую — <=

А данные в 0..n-1, да

что дятлом по дубу, что дубом по дятлу.

ты предлагаеш запомнить молитву.

при том что она выводится(но многие постоянно фейлят - в том числе и я)

у мя есть даже не в памяти , а просто напросто при решение вот это трёх путевое.

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

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

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

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

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

т.е просто заучить сам код ?

Нет, переписать очевидный код, а потом проверить, что получилось именно то, что хотелось изначально

хм. т.е сохранить симметрию границ(на 1 меньше меньшего и на 1 больше большего)

и нарушать только в условии (для определения какой край предпочтителен)

дык код не очевиден(лично мне, очевиден трёхпутевой с границами ровно по краям)

отсюда и затруднение как «догадыватся»

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

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

это твой опенсорс проект?

А я-то было подумал, что ты перестал упарываться...

проблема как из 3 очевидных альтернатив формулировать равномощный(т.е охватывающий все те же случаи ) 2ух альтернативный.

не существует такого преобразования.

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

0:return m;

0:r=m; l=m+1;
или
0:r=m-1; l=m;

-1:r=m-1;
 0:l=m+1;
 1:l=m+1;
или
-1:r=m-1;
 0:r=m-1;
 1:l=m+1;

может я не правильно понял то, что требовалось.

не. ясно что 3путёвой не эквивалентен 2путевому

в 1случае возвращаем первый попавшийся индекс

а во втором тот или иной край(зависит от «согласованости» выбора середины и к какой ветке её при делении относить).

я про то что (вон вариант с инициализацией -1,n и условием r-l>1 пока наиболее «запоминающийся» из двухпутевых) как по максимуму охранить симметричность(ибо это мне лично облегчает правильность воспроизведения сего алгоритма)

чувствует сле^Wшпора «царя»

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

второй случай ещё и усугублён использованием бинарного if

где этот оператор if?

а ещё, можно вернуться к формулировке цели задачи и точно её описать?

во втором случае показано что ветка == совпадает с одним из оставшихся вариантов . т.е по факту место выбора из 3 выбор из 2 вариантов.

задача:

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

какое минимальное число и каких «хинтов» помнить что- бы получать с ходу «классический» несиметричный бинпоиск ( тот который находит не первый попавшийся ,а всегда с одного и тогоже края если их(искомых)много ну и до /после если искомое ниженижнего/вышевышнего)

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

почему во втором алгоритме условие "-1" стало с измененным кодом? он ведь ухудшил скорость работы.

извиняюсь, нашел фразу:

тот который находит не первый попавшийся

итак, нужно запомнить 3 пункта:

• выходить из цикла по равенству границ,
• при равенстве key и v[m] сдвигать границу противоположную искомой:
  • при поиске левой границы сдвигать правую,
  • при поиске правой границы сдвигать левую.
• в конце работы проверить равенство key и v[r] (или v[l], по первому пункту без разницы что брать) и вернуть нужное значение.

пример:

l,r=0,n
while(l<=r){
  m=l+(r-l)/2;
  sign(cmp(key,v[m])):
    -1:r=m-1;
     0:return m;
     1:l=m+1;
  }
return "-1 /что по мнению Степанова не культурно"

l,r=0,n
while(l<r){ // первый пункт
  m=l+(r-l)/2;
  sign(cmp(key,v[m])):
    -1:r=m-1;
     0:r=m; // второй пункт
     1:l=m+1;
  }
cmp(key,v[r]): // третий пункт
  return r
return "-1 /что по мнению Степанова не культурно"