1

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

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, а хочется понять. Есть ли какое-то объяснение, как лучше понять механику работы этого условия?

1
  • 3
    А если ширина диапазона равна один элемент - то чему будет равно left и right? Вот тут и появляется интересный момент на котором одно из условий ("неправильное") не сработает.
    – nick_n_a
    Commented 7 июн. 2021 в 9:46

1 ответ 1

2

В принципе можно использовать строгое неравенство, но в этом случае необходимо проверить после цикла, что элемент nums[l] равен target.

Пример - массив из двух элементов [0, 2], ищем target = 1.

В первой итерации l = 0, r = 1, mid = 0.

Тогда nums[mid] == 0, то есть nums[mid] < target. Следовательно, l становится равным 1. Цикл while (l<r) { ... } завершается. Но l нельзя вернуть, так как nums[1] != target. Поэтому перед выходом надо проверить, что лежит в массиве по индексу 1.

public int Search(int[] nums, int target)
{
    // UPDATE добавлена обработка пустого массива
    if (0 == nums.Length) { return -1; }

    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 (nums[left] == target)? left : -1;
}
4
  • 1
    Очень неожиданный вариант, я глядел на комментарий nick_n_a и думал, что именно его версию в ответ кто-нибудь впишет. Но чем он мне нравится -- так это тем, что этот вариант пробрасывает логический мостик от простой формы бин.поиска к поиску leftmost/rightmost элемента (следующий шаг: переносим проверку if(nums[mid] == target) return mid; за пределы цикла) и это для меня неожиданная, но очень полезная находка, спасибо! Галку в этом вопросе ставить не буду -- всё-таки он основан на мнениях, разным участникам может другая версия понравится.
    – A K
    Commented 7 июн. 2021 в 13:26
  • 3
    +1, но ваш вариант падает на пустом массиве.
    – VladD
    Commented 7 июн. 2021 в 14:27
  • @VladD спасибо )))
    – Pak Uula
    Commented 8 июн. 2021 в 3:47
  • 2
    Если уж говорить о бинарном поиске, возможно, имеет смысл возвращать не -1, когда элемент не найден, а индекс для вставки, как это делает, например, Array.BinarySearch. При этом инварианты (наподобие nums[i] <= target при i <= left) начинают становиться важнее.
    – VladD
    Commented 8 июн. 2021 в 12:28

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.