Binary Search Out of Range

Question

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 conclusion:

I looked at this world of code to get more than necessary, and still cannot figure out where the error is.

Answer 1

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

last = middle - 1

causes integer overflow; conditions should be reworked a bit.

Answer 2

, (first, last, middle) unsigned int, last . , unsigned - , , while - .

:

#include <stdio.h>

int main() {
  /* defining the variables as unsigned */
  unsigned int first_u = 0;
  unsigned int last_u = -1;

  if (first_u <= last_u)
    printf("less than\n");
  else
    printf("greater or equal\n");

  /* defining the variables as signed */
  int first_s = 0;
  int last_s = -1;

  if (first_s <= last_s)
    printf("less than\n");
  else
    printf("greater or equal\n");

  return 0;
}

, < while -condition last size-1. , , , , .

Answer 3

-, (unsigned int).

, : unsigned int last = size-1, , last = size, ptrToArray [] = , . = 0.

, , : middle =(first+last)/2, [, ] equals to first+(last-first)/2.

Answer 4

, , , , , - , , last first while (first <= last)

, , : size == 0:

first = 0, last = 0And thus: (first <= last) == true.
Then, middle = 0 + (0 - 0)/2 = 0and then you will get access to ptrToArray[0]that which is not connected.