Ziezi Ziezi - 2 months ago 12
C Question

Binary search accessing out of range index

This is the code:

char binarySearch(unsigned int target, int* primes, unsigned int size){
int* ptrToArray = primes;
unsigned int first = 0;
unsigned int last = size;

while (first <= last){
unsigned int middle = first + (last - first) / 2;
printf("first: %d, last: %d, middle: %d\n", first, last , middle);

if (ptrToArray[middle] == target){
return 1;
}

if (ptrToArray[middle] < target){
first = middle + 1;
}else{
last = middle - 1;
}
}
return 0;
}


This is the output:

enter image description here

I've been staring at that peace of code for more than one should and still can't figure out where is the flaw.

Answer

If middle is 0, as near the end of your debug output, the statement

last = middle - 1

causes an integer overflow; the conditions have to be reworked a bit.

Comments