В вашей реализации неверно отрабатывал вариант, когда вы в качестве x
передаете переменную, значение которой больше любого элемента массива (правда на самом деле у вас vector
, а не массив, но не суть), а также в конце вы сравниваете с A[0]
, а не с A[left]
, хотя по логике вещей с ним бы и нужно сравнивать (ведь вы в границах диапазона решаете задачу, по крайней мере судя по входным параметрам).
В вашем коде минимальными усилиями можно решить данную проблему если заменить вот этот кусок:
if (x <= A[0])
{
return 0;
}
на следующий:
if (x <= A[left])
return 0;
else if (x > A[right])
return (right - left + 1);
Кстати, будет эффективнее, если вы эту проверку переместите в начало процедуры, а не в конец.
Ну и в начале неплохо бы проверять left
и right
на вхождение в границы диапазона (ну и что left <= right
), а то в итоге mid
, через значение которого по индексу вы затем обращаетесь, может выйти из них.
А еще экземпляр vector
'а передавайте по ссылке с модификатором const
(не вы же не меняете объект внутри функции), чтобы в лишний раз не вызывать конструктор копирования.
Либо можно несколько поменять логику работы:
int binary_search(const std::vector<int>& arr, int key, int left, int right)
{
left = (left < 0) ? 0 : left;
right = (right > arr.size() - 1) ? arr.size() - 1 : right;
do
{
int middle = (left + right) / 2;
if (key < arr[middle])
right = middle - 1;
else if (key > arr[middle])
left = middle + 1;
else
{
for (; (middle >= 0) && (key == arr[middle]); --middle){}
return middle + 1;
}
if (left > right)
return left;
} while (true);
}