Абстрактная задача для понимания реализации бинарного поиска

Имеется массив A из N элементов типа L и R. Причем, сначала последовательно идут элементы типа L, затем элементы типа R. Мы хотим найти в массиве переход из L в R.
Очевидно, что эту задачу можно решить за линейное время. Ниже показан алгоритм решения за время log(N).
Договоримся индексировать не элементы а границы между элементами. Так для массива из N элементов самая левая граница имеет индекс 0, самая правая индекс N. Нашей задачей будет найти индекс границы между двумя соседними элементами, так что слева от границы находится элемент L, а справа находится элемент R.

Примеры:

N = 5;
0 1 2 3 4 5
|L|L|R|R|R| -> 2
|L|L|L|L|L| -> 5 (добавляем в конец массива фиктивный элемент R)
|R|R|R|R|R| -> 0 (добавляем в начало массива фиктивный элемент L)

Получаем следующую реализацию:

int bsearch(int A[], int N) {
int lo = 0;
int hi = N;
while (lo != hi) {
int mid = (lo + hi) / 2;
int val = A[mid];
if (val == 'L') {
lo = mid + 1;
} else {
hi = mid;
}
}
int pos = lo;
return pos;
}

На каждой итерации цикла мы определяем индекс границы, находящийся между lo и hi. Очевидно, что lo<=midВ случае равенства R интервал сужается до (lo, mid). На выходе мы имеем индекс границы 0 <= pos <= N. В случае равенства нулю, все элементы равны R. Если равно N, то все элементы L.