Как реализовать правосторонний бинарный поиск?

Question

[rastr]

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

long long right_binary_search(std::vector<long long>& one, long long num)
{
	long long l = 0, r = one.size() - 1;
	while (l < r)
	{
		long long mid = l + (r - l) / 2;
		if (one[mid] == num)
		{
			return mid;
		}
		else if (one[mid] < num)
			l = mid + 1;
		else if (one[mid] >= num)
			r = mid - 1;
	}
	if (one[l] == num)
		return l;
	else
		return -1;
}

Comments

[Sun_Day]

Вы вообще в курсе как бинарный поиск работает? Что вы хотите, объясните подробнее.

[rastr]

Sun_Day, Мне надо, чтобы поиск выводил индекс самого правого значения в массиве, которое задано найти, при наличие нескольких одинаковых элементов.
1 1 3 3 (найти 3) - ответ 3; найти(1) - ответ 1.

[Sun_Day]

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

[Евгений Шатунов]

rastr, long long mid = l + (r - l) / 2;
Почему эта строка написана именно так? Что будет если убрать деление? Что будет если убрать вычитание единицы?

[rastr]

Евгений Шатунов, это l, от left. В студии шрифт странный) А написана так, дабы избежать переполнения, потому что на тестах там большие числа.

Answer 1

[Wataru]

Уберите проверку на совпадение внутри while. Присваивайте границам интервала mid, а не mid+1 или -1.