Finding the number of occurrences of a number in a sorted array with O(log(N)) in C?

Question

If i have a sorted array arr[] conatains n eleemnts, how can I find the number of occurrences of a certain number key with the complexity of O(logn)?

For example: for

int arr[] = {0, 1, 2, 2, 6, 6, 6, 7};
int n = 8;
int key = 6;
int first, last;

I will get 3.

My approach to the problem was by doing two binary searches, one searches for the index of first occurrence of key, saving the result in int first. And another one searches for the index of the last occurrence of key, saving the result in last. Then the only thing left to do is to return last - first + 1.

But when I started to code the problem, I came into a problem, I couldnt calculate last what resulted strange results. I have been trying to debug my code but with no success, Any suggestions?

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int ex2(int*, int, int);

int main()
{
    int arr[] = {1, 4, 6, 6, 6, 7, 7, 8, 11, 14, 22};
    printf("%d", ex2(arr, 11, 6));
    return 0;
}

int ex2(int* a, int n, int x)
{
    int low = 0, high = n - 1, mid, first = 0, last = 0;
    // bin first
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] == x)
        {
            if (mid - 1 < low || a[mid - 1] < x)
            {
                first = mid;
                break;
            }
            else
                high = mid - 1;
        }
        if (a[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    // bin last
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (a[mid] == x)
        {
            if (mid + 1 > high|| a[mid + 1] > x)
            {
                last = mid;
                break;
            }
            else
                low = mid + 1;
        }
        if (a[mid] < x)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return last - first + 1;

}

When I run it for:

    int arr[] = {1, 4, 6, 6, 6, 7, 7, 8, 11, 14, 22};
    printf("%d", ex2(arr, 11, 6));

I get -1 (Becuase last is still 0 unlike first which holds the right value of 2 - > 0 - 2 + 1 = -1). When I sould get 3 (6 appears 3 times).

Answer 1

Change if (a[mid] < x) to else if (a[mid] < x) both places it appears.

Otherwise, in the case where a[mid] == x and you set low (in the first search) or high (in the second search), the code then falls through to this test of a[mid] < x and sets the other bound, incorrectly. Inserting the else excludes that.