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

Question

[Дмитрий Митин]

Добрый день.
Сижу второй день не могу понять как написать рекурсивный бинарный поиск.
Задание состоит в следующем, найти индекс левой границы

, а в случае если искомого элемента в таблице нет, вернуть -1;
Код должен быть именно рекурсивным.

private static int FindLeftBorder(long[] arr, long value)
{
	return BinSearchLeftBorder(arr, value, -1, arr.Length);
}

Я написал код, но никак не могу понять, как возвращать -1?

public static int BinSearchLeftBorder(long[] array, long value, int left, int right)
		{
			if (left == right) return left;
			var m = (left + right) / 2;
			if (array[m] < value)
				return BinSearchLeftBorder(array, value, m, right-1 );
			return BinSearchLeftBorder(array, value, left, m);
		}

Я очень ещё начинающий любитель, поэтому прошу прощения сразу за глупость данного вопроса.
Заранее Спасибо всем за ответ!

Comments

[Maxim Isaev]

в итоге разобрались?

Answer 1

[AlexHell]

смысл бинарного поиска это постепенное сдвигание границ, т.е [0, 10] интервал для array превращается в [0, 5] потом в [2, 5] потом в [4,5] потом проверяется элемент [4]

За точность не гарантируюю, но то что пришло на ум
public static int BinSearchLeftBorder(long[] array, long value, int left, int right)
{
if (left == right)
{
if (array[left] == value) return left;
return -1;
}

var m = (left + right) / 2;
if (array[m] < value)
return BinSearchLeftBorder(array, value, m, right-1 );
return BinSearchLeftBorder(array, value, left, m);
}

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

для вашего примера с 2 прямо по середине, бин-поиск обычный завершится сразу на 1м шаге и найдет в индексе [4] значение == 2.