How to return positive occurrence

Question

I have a function that when given a zero-indexed array A of N integers, sorted in non decreasing order, and some integer X, looks for X in A. If X is present in A, then it returns a positive index of an occurrence of X in A. Otherwise, the functions returns -1.

It should work like this:

• If I have A[0]=1, A[1]=1 and X=1 it should return 0 because A[0]=1.

But it doesn't return what I want. Can someone help me? Here is my code:

int Number(int *A, int N, int X) {
    int r, m, l;
    if (N == 0) {
        return -1;
    }
    l = 0;
    r = N - 1;
    while (l < r) {
        m = (l + r) / 2;
        if (A[m] > X)  {
            r = m - 1;
        } else {
            l = m;
        }
    }
    if (A[l] == X) {
        return l;
    }
    return -1;
}

Answer 1

Binary Search does not guarantee that the found position is a first occurence of this number in an array.

if I have A[0]=1, A[1]=1 and X=1 it should return 0 because A[0]=1

It means that in this sutiation the answer "1" is correct because A[1] = 1 as well.

You need to manually iterate through the array to find the first non-matching value (or array beginning). Optimizations are possible but they are only necessary if you have an extremely big arrays with high number of value repetitions.

Also you can try a default binary search approach:

int Number(int *A, int N, int X) {
    int r, m, l;
    if (N == 0) {
        return -1;
    }
    l = 0;
    r = N - 1;
    while (l < r) {
        m = (l + r) / 2;
        if (A[m] == X)
           return m;
        if (A[m] > X)  {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

Answer 2

I tried a slightly different strategy. It seems to work.

#include <stdio.h>

int Number(int *A, int N, int X) {
    int r, m, l;
    if (N == 0) {
        return -1;
    }
    l = 0;
    r = N; // Not N-1
    while (l < r) {
       m = (l + r) / 2;

       // Debugging output. Track how l, m, and r change.
       printf("l: %d, m: %d, r: %d\n", l, m, r);

       // A slightly different strategy for narrowing
       // the interval.
       if (A[m] < X)  {
          l = m+1;
       } else {
          r = m;
       }
    }
    if (A[l] == X) {
        return l;
    }
    return -1;
}

void test1()
{
   int A[] = {1, 1};
   printf("%d\n", Number(A, 2, 1));
}

void test2()
{
   int A[] = {0, 1, 1};
   printf("%d\n", Number(A, 3, 1));
}

void test3()
{
   int A[] = {0, 0, 1, 1, 2, 2};
   printf("%d\n", Number(A, 6, 1));
   printf("%d\n", Number(A, 5, 1));
   printf("%d\n", Number(A, 4, 1));
}

int main()
{
   test1();
   test2();
   test3();
   return 0;
}

Output:

l: 0, m: 1, r: 2
l: 0, m: 0, r: 1
0
l: 0, m: 1, r: 3
l: 0, m: 0, r: 1
1
l: 0, m: 3, r: 6
l: 0, m: 1, r: 3
l: 2, m: 2, r: 3
2
l: 0, m: 2, r: 5
l: 0, m: 1, r: 2
2
l: 0, m: 2, r: 4
l: 0, m: 1, r: 2
2

Answer 3

Here is a modified binary search from Jon Bentley's book Programming Pearls, 2nd Edition:

/*
** Modified binary search.
** Find lowest occurrence of value in array (if there is more than one)
*/

#include <assert.h>
#include <stdio.h>

/*
** From J Bentley "Programming Pearls, 2nd Edition", Section 9.3
** Locate the first occurrence of t in x[0..n-1].
** Assume n >= 0, and the hypothetical elements x[-1] < t and x[n] > t
** without accessing either fictitious element.
*/
static
int bsearchf(const int *x, int n, int t)
{
    int l = -1;
    int u = n;

    assert(n >= 0);
    while (l + 1 != u)
    {
        /* Invariant: x[l] < t && x[u] >= t && l < u */
        int m = (l + u) / 2;
        //printf("  t = %d, l = %d, u = %d, m = %d, x[%d] = %d\n",
        //       t, l, u, m, m, x[m]);
        if (x[m] < t)
            l = m;
        else
            u = m;
    }
    if (u >= n || x[u] != t)
        return -1;
    assert(u >= 0 && u < n);
    return u;
}

int main(void)
{
    const int data[] =
    {
        0, 0, 0, 2, 2, 2,
     /* 2, 2, 2, 2, 2, 2, */
        4, 6, 6, 6, 8, 8,
    };
    enum { DATA_SIZE = sizeof(data) / sizeof(data[0]) };

    /* Check monotonic non-decreasing data */
    for (int j = 0; j < DATA_SIZE - 1; j++)
        assert(data[j] <= data[j+1]);

    /* Every starting point in the data array */
    for (int j = 0; j < DATA_SIZE; j++)
    {
        const int *base = &data[j];
        /* Every valid data length for the remainder of the data array */
        for (int k = DATA_SIZE - j; k > 0; k--)
        {
            int lo = base[0] - 1;
            int hi = base[k-1] + 2;

            printf("N = %d", k);
            for (int m = 0; m < k; m++)
                printf(" A[%d]: %d", m, base[m]);
            putchar('\n');

            /* For every value from 1 less than the minimum to one more than the maximum */
            for (int i = lo; i < hi; i++)
            {
                int r = bsearchf(base, k, i);
                printf("V = %2d, : R = %2d, C = %2d : %s\n",
                        i, r, (r < 0) ? -1 : base[r],
                        (r < 0) ? "missing" : "found");
                if (r == -1)
                {
                    for (int n = 0; n < k; n++)
                        assert(base[n] != i);
                }
                assert(r == -1 || (base[r] == i && (r == 0 || base[r-1] < i)));
            }
        }
    }

    return 0;
}

The main program is a tester which checks every subsequence of the array data and tries to find every number between min - 1 and max + 1 in that array, many of which are not found of course since there are only even values in the array. It is verbose in its output, but there are assertions to give its results teeth: an assertion should fire if there is a problem with the result.

Answer 4

You can do it through searching!

Try this one!

public class MyClass {
   public static void main(String[] args) {
        int a[] = {1,2,3,4,5,6,9,12,55,123};
        int x = solution(a,1);
        System.out.println(x);
    }
    
public static int solution(int[] A, int X) {
                int N = A.length;
                int r, m, l;
                if (N == 0) {
                    return -1;
                }
                l = 0;
                r = N;
                while (l < r) {
                    m = (l +r)/2;
                     if (A[l] == X)
                    return l;
                    if (A[m] > X)  {
                        r = m - 1;
                    } else {
                        l = m ;
                    }
                }
                return -1;
        }
}