Есть нижеследующий алгоритм двоичного поиска.

desiredValue // искомое значение
int a[N]; // массив, где проводится поиск
int left = 0; // левая граница поиска
int right = N; // правая граница поиска
int middle; // среднее значение
while (left < right)
{
    middle = left +  (right - left) / 2;
    if (a[middle] < desiredValue)
        left = middle + 1;
    else
        right = middle;
}
if (a[right] == desiredValue)
    return right;
else
    return -1;

Я не до конца понимаю как работает этот алгоритм. У меня возникает множество вопросов почему.
Например:
1) Я хочу доказать, что результат работы при успешном поиске будет находится в right.
Суть работы алгоритма, в моём понимании, это разделить задачу на мелкие подзадачи
до тех пор пока не останется неделимая задача и тогда можно будет решить её. И... не соображаю дальше как это связать с кодом выше.

2) Доказать, что найденное значение является первым среди возможных одинаковых значений. Тут я смутно понимаю, что это как-то связано с тем, что массив наш отсортирован, но дальше не вижу куда двигаться.
3) Почему при a[middle] < desiredValue мы делаем left = middle + 1? Не получится ли так, что из-за такой границы мы не учтём один элемент? Так то я понимаю, что если не делать middle + 1, то мы никогда не выйдем из цикла. Но вот как выразить это присваивание словами?

У Кнута для лучшего понимания нарисовано двоичное дерево. Действительно, как я увидел тот рисунок двоичного дерева, у меня не возникают все эти вопросы почему, но сейчас то у меня простой массив и у меня сомнения, что двоичное дерево можно просто взять и наложить на массив.


Прошу помочь разобраться с этими вопросами. Я действительно не вижу как это работает.