CODEWITHSUNDEEP
c
Mingfeng Li
Mingfeng Li

Reputation: 45

Missing number in sorted array

This code is designed to find the missing element in the sorted array, but it fails the second test. What is my error?

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

int a[] = { 4, 5, 7, 8, 9 };
int b[] = { 4, 5, 6, 8, 9, 10 };
int c[] = { 4, 6, 7, 8, 9, 10 };
int d[] = { 4, 5, 6, 7, 9, 10 };
int e[] = { 4, 5, 6, 7, 8, 9 };

int findMissing(int *a, int len) {
    int L = 0;
    int R = len - 1;
    int mid;
    while (R - L > 1) {
        mid = (L + R) / 2;
        if (a[L] - L != a[mid] - mid)
            R = mid;
        else if (a[R] - R != a[mid] - mid)
            L = mid;
    }
    return a[mid] + 1;
}

main() {
    assert( findMissing( a, 5 ) == 6 );
    assert( findMissing( b, 6 ) == 7 );
    assert( findMissing( c, 6 ) == 5 );
    assert( findMissing( d, 6 ) == 8 );
    assert( findMissing( e, 6 ) == 10 );
}

Upvotes: 1

Views: 99

Answers (1)

chqrlie
chqrlie

Reputation: 144780

The algorithm has problems:

  • mid is used uninitialized if len <= 2
  • there is no need for the second test, just test the initial boundaries
  • furthermore main() should have a return type int.

Here is a modified version:

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

static int a[] = { 4, 5, 7, 8, 9 };
static int b[] = { 4, 5, 6, 8, 9, 10 };
static int c[] = { 4, 6, 7, 8, 9, 10 };
static int d[] = { 4, 5, 6, 7, 9, 10 };
static int e[] = { 4, 5, 6, 7, 8, 9 };

int findMissing(const int *a, int len) {
    int L = 0;
    int R = len - 1;
    if (len <= 0) {
        // no number
        return 0;
    }
    if (a[0] == a[R] - R) {
        // no missing number
        return a[R] + 1;
    }
    while (R - L > 1) {
        int mid = L + (R - L) / 2;
        if (a[0] != a[mid] - mid)
            R = mid;
        else
            L = mid;
    }
    return a[0] + R;
}

int main() {
    assert( findMissing( a, 5 ) == 6 );
    assert( findMissing( b, 6 ) == 7 );
    assert( findMissing( c, 6 ) == 5 );
    assert( findMissing( d, 6 ) == 8 );
    assert( findMissing( e, 6 ) == 10 );
    return 0;
}

Upvotes: 3

Related Questions