CODEWITHSUNDEEP
carrayspointers
user9586643
user9586643

Reputation:

Getting invalid position on the array

I am writing a program that reads a list of values, and 3 values, a, b, elem. I wrote a function which finds if the element is part of the array between the position a and b. When I run the program sometimes i get right results sometimes i get wrong results. I can't find the mistake. Any help would be welcomed.

int binary_search(int *v, int elem, int a, int b);

int main()
{
    printf("Inserire la lunghexza di N:\n");
    int N;
    scanf("%d", &N);
    printf("Inserire i valori dell'array:\n");
    int arr[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    int a,b,elem;
    printf("Inserire i valori di a, b, elem:\n");
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &elem);
    printf("%d", binary_search(arr,elem,a,b));
    return 0;
}

int binary_search(int *v, int elem, int a, int b)
{
    for (int i = 0; i < i < b - a; i++) {
        if (*(v + a - 1 + i) == elem) {
            return a + i;
        }
    }
    return -1;
}

Upvotes: 1

Views: 243

Answers (2)

H.S.
H.S.

Reputation: 12669

As the other answer already pointed out that the expression i < i < b - a in for loop condition is weird but it doesn't explain why?

for (int i = 0; i < i < b - a; i++)
                ^^^^^^^^^^^^^

Aren't you getting any compiler warning on this expression? If yes, one suggestion - warnings are there for some reason, don't ignore them.

In the expression i < i < b - a, assume that b - a results in x. So, the expression i < i < x will be evaluated as (i < i) < x (as the associativity of operator < is left to right) in which (i < i) will always result in false and whole expression will always result in true for all valid** values of a and b which satisfy the condition b > a and if the elem value does not exists in array then due to this condition

if (*(v + a - 1 + i) == elem) {
    ^^^^^^^^^^^^^^^^

your program end up accessing array out of bound which is undefined behavior.

So, first of all correct the for loop condition by removing extra i <:

for (int i = 0; i < b - a; i++)

Now, with this, the loop will check the values starting from ath element till b - 1th element in the array.

Also, following is more readable as compare to your current version of binary_search():

int binary_search(int *v, int elem, int a, int b)
{
    for (int i = a - 1; i < b; i++) {
        if (v[i] == elem) {
            return i;
        }
    }
    return -1;
}

There is another problem in your program - **your program is not checking the validity of user input a and b. It may be possible that user accidentally input the value of a and/or b which is not in the range of array or negative value or value of a greater than b etc. You should check the validity of user input as well.

PS: I assume that, you are very well aware of fact that, in your program, the binary_search() function is doing linear search and the binary search need the input array in sorted order.

Upvotes: 0

skratpa
skratpa

Reputation: 130

Like Adrian already pointed out, this line seems kind of weird: 

for (int i = 0; i < i < b - a; i++)

Did you mean:

for (int i = 0; i < b - a; i++)

Upvotes: 2

Related Questions