Сколько я не видел материалов по бинарному поиску - все описывают простейшую форму бинарного поиска в таком виде:
public int Search(int[] nums, int target)
{
var left = 0;
var right = nums.Length - 1;
while (left <= right)
{
var mid = left + (right - left)/2;
if(nums[mid] == target)
return mid;
if(nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
И я всё время сколько пишу бинарные поиски задумываюсь о том, как мне логически объяснить почему в цикле while стоит условие left <= right
, а не left < right
? Каждый раз сижу и задумываюсь, какой знак поставить, а главное -- почему так?
Как ни странно, но нигде нет объяснения, возможно это настолько очевидно, что даже пояснять не надо? Прямо говоря, мне не очень хочется запоминать этот факт as is, а хочется понять. Есть ли какое-то объяснение, как лучше понять механику работы этого условия?