c++ – Find the number of elements in an array less than a given one

Question:

It was necessary to find the number of array elements less than the one specified in the sorted array without repetitions. Moreover, this must be done as quickly as possible. I used binsearch, this is what I got.

For some reason, it doesn't always work. What could be the problem?

int binary_search(std::vector<int> A, int x, int left, int right)
{
   while (right - left > 1)
   {
      int mid = (left + right) / 2;
      if (A[mid] < x)
      {
         left = mid;
      }
      else
      {
         right = mid;
      }
   }
   if (x <= A[0])
   {
      return 0;
   }
   return left + 1;
}

Answer:

In your implementation, I incorrectly worked out the option when you pass a variable as x , the value of which is greater than any element of the array (though in fact you have a vector , not an array, but not the essence), and also at the end you compare with A[0] , and not with A[left] , although logically it would be necessary to compare with it (after all, you are solving the problem within the range, at least judging by the input parameters).

In your code, with minimal effort, you can solve this problem if you replace this piece:

if (x <= A[0])
{
    return 0;
}

to the next:

if (x <= A[left])
   return 0;
else if (x > A[right])
   return (right - left + 1);

By the way, it will be more efficient if you move this check to the beginning of the procedure, and not to the end.

Well, at the beginning it would be nice to check left and right for entering the range boundaries (so what is left <= right ), otherwise, as a result, mid , through the value of which by index you then refer to, may exit them.

And also pass the vector instance by reference with the const modifier (you don't change the object inside the function), so as not to call the copy constructor once again.

---

Or, you can slightly change the logic of work:

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);
}